30. String all the words together

If we look at the word as a whole, it becomes something like find the longest unrepeated character substring in a string, in order to get the full traversal space.

Assuming array length * word length =k, to traverse all possibilities, we need [0~n-k] words as a starting point to determine whether it is possible.

In fact, what we need to consider is that if we move in units of word length, starting with each character of the first word, we can find all of the possibilities that are equivalent.

Concrete modeling can then be done:

Define left and right, and ensure that all items within the range [left,right] are in the legal state (each word is in the word array, and the number does not exceed), as long as the extension is such that each word has the same number, that is the answer.

Once you find the answer, you need to find the answer space again by moving left one to the right.

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (words == null || words.length == 0) return ans;
        HashMap<String, Integer> set = new HashMap<>();
        for (String i : words) set.put(i, set.getOrDefault(i, 0) + 1);
        int len = words[0].length();
        for (int i = 0; i < len; i++) {
            HashMap<String, Integer> judge = new HashMap<>();
            int left = i, right = i;
            for (; right <= s.length() - len; right += len) {
                String t = s.substring(right, right + len);
                if(! set.containsKey(t)) {for (; left < right; left += len) {
                        String tt = s.substring(left, left + len);
                        judge.put(tt, judge.getOrDefault(tt, 1) - 1);
                    }
                    left += len;
                    continue;
                }
                else if (judge.getOrDefault(t,0)>=set.get(t)){
                    for (; judge.get(t)>=set.get(t); left += len) {
                        String tt = s.substring(left, left + len);
                        judge.put(tt, judge.getOrDefault(tt, 1) - 1); }}if (set.containsKey(t)) judge.put(t, judge.getOrDefault(t, 0) + 1);
                if (set.size() == judge.size()) {
                    boolean isChecked = true;
                    for (Map.Entry<String, Integer> entry : set.entrySet()) {
                        if(! judge.getOrDefault(entry.getKey(),0).equals(entry.getValue())) {
                            isChecked = false;
                            break; }}if (isChecked) {
                        ans.add(left);
                        String tt = s.substring(left, left + len);
                        judge.put(tt, judge.getOrDefault(tt, 1) - 1); left += len; }}}}return ans;
    }
Copy the code