Substring with Concatenation of All Words(Hard)

Leetcode Source

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given: s: "barfoothefoobarman"

words: ["foo", "bar"]

You should return the indices: [0,9].

(order does not matter).

解题思路：双指针+双HashMap

需要用到的内存空间：

1. 两张哈希表，一张保存L集合中的单词，一张用来保存当前滑块中的单词，key为单词，value为出现次数
2. cout计数，保存当前滑块中的单词总数
3. left标记，记录滑块左起点

Java代码

public List<Integer> findSubstring2(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (S == null || S.length() == 0 || L == null || L.length == 0)
            return result;
        int strLen = S.length();
        int wordLen = L[0].length();
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        //1 遍历一遍单词数组L集合，构造总单词表
        for (int i = 0; i < L.length; i++) {
            if (map.containsKey(L[i])) {
                map.put(L[i], map.get(L[i]) + 1);
            } else {
                map.put(L[i], 1);
            }
        }

        for (int i = 0; i < wordLen; i++) {
            HashMap<String, Integer> curMap = new HashMap<String, Integer>();
            int count = 0, left = i;

            //2 以单词长度为步长，遍历目标字符串
            for (int right = i; right <= strLen - wordLen; right += wordLen) {
                String curStr = S.substring(right, right + wordLen);
                if (map.containsKey(curStr)) {
                    //3 如果当前单词在总单词表内，当前滑块单词表中的相应单词计数加1
                    if (curMap.containsKey(curStr)) {
                        curMap.put(curStr, curMap.get(curStr) + 1);
                    } else {
                        curMap.put(curStr, 1);
                    }

                    //检查该单词的计数是否小于等于总单词表中该单词的总数,如果是，则将count计数加1
                    if (curMap.get(curStr) <= map.get(curStr)) {
                        count++;
                    } else {
                //4 根据左起点left收缩滑块，直到收缩到与当前单词相同的字符串片段，将其剔除之后，滑块的收缩工作完成
                        while (true) {
                            String tmp = S.substring(left, left + wordLen);
                            curMap.put(tmp, curMap.get(tmp) - 1);
                            left += wordLen;
                            if (curStr.equals(tmp)) {
                                break;
                            } else {
                                count--;
                            }
                        }
                    }

                    //5 如果当前count计数等于单词集合长度，记录下left左起点的位置后，将left右移，当前滑块中相应单词计数减1，总计数减1，继续循环
                    if (count == L.length) {
                        result.add(left);
                        String tmp = S.substring(left, left + wordLen);
                        curMap.put(tmp, curMap.get(tmp) - 1);
                        left += wordLen;
                        count--;
                    }
                } else {
                    //反之，则清空当前滑块单词表，将cout置零，将left移动到下一位置
                    curMap.clear();
                    count = 0;
                    left = right + wordLen;
                }
            }//inner for

        }
        return result;
    }

References

1. Substring with Concatenation of All Words From SegmentFalt

2. Minimum Window Substring(Hard)最小窗口子串