LeetCode 30 - Substring with Concatenation of All Words

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

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

public List<Integer> findSubstring(String S, String[] L) {
    List<Integer> result = new ArrayList<Integer>();
    int len = L[0].length();
    if(L.length==0 || len == 0 || len>S.length()) return result;
    
    Map<String, Integer> map = new HashMap<>();
    for(String str: L) {
        map.put(str, map.containsKey(str)?map.get(str)+1:1);
    }
    
    int wordLen = len * L.length;
    Map<String, Integer> map2 = new HashMap<>();
    for(int i=0; i<=S.length()-wordLen; i++) {
        map2.clear();
        String word = S.substring(i, i+wordLen);
        boolean found = true;
        for(int j=0; j<=word.length()-len; j += len) {
            String slice = word.substring(j, j+len);
            if(map.containsKey(slice)) {
                int count = map2.containsKey(slice) ? map2.get(slice)+1 : 1;
                map2.put(slice, count);
                if(count > map.get(slice)) {
                    found = false;
                    break;
                }
            } else {
                found = false;
                break;
            }
        }
        if(found) {
            result.add(i);
        }
    }
    
    return result;
}

 

又重构了一下代码，结构更加清晰。

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> list = new ArrayList<>();
    int L = s.length(), N = words[0].length();
    int M = N * words.length;
    if(L == 0 || N == 0 || M > L) return list;
    Map<String, Integer> dict = new HashMap<>();
    for(String word:words) {
        Integer cnt = dict.get(word);
        dict.put(word, cnt == null ? 1 : cnt+1);
    }
    for(int i=0; i<=L-M; i++) {
        String str = s.substring(i, i+M);
        if(containWords(str, words, dict)) {
            list.add(i);
        }
    }
    return list;
}

private boolean containWords(String str, String[] words, Map<String, Integer> dict) {
    int N = words[0].length();
    Map<String, Integer> map = new HashMap<>();
    for(int i=0; i<str.length(); i+=N) {
        String word = str.substring(i, i+N);
        Integer cnt = map.get(word);
        cnt = cnt == null ? 1 : cnt+1;
        map.put(word, cnt);
        if(!dict.containsKey(word) || cnt > dict.get(word)) return false;
    }
    return true;
}

 

补充个C++的代码：

vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> result;
    if(words.empty()) return result;
    unordered_map<string, int> map;
    for(auto& word:words) {
        map[word]++;
    }
    int n = words.size(), m = words[0].size();
    int l = m * n, len = s.size();
    for(int i=0; i<=len-l; i++) {
        string t = s.substr(i, l);
        if(contains(map, t, m)) 
            result.push_back(i);
    }
    return result;
}
bool contains(unordered_map<string, int> map, string& s, int m) {
    for(int i=0; i<=s.size()-m; i+=m) {
        string t = s.substr(i, m);
        if(map[t]--<=0) return false;
    }
    return true;
}

 

还有另外一种更加高效的代码，滑动窗口的方法：

首先是要明确用滑块的概念来解决，始终保持L集合中的字符串在滑块中都只出现了一次，当然设置一个总计数count，当cout等于L集合长度时，即使找了一段符合要求的字符串。

需要用到的内存空间：

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

实现的步骤：

1. 遍历一遍单词数组L集合，构造总单词表
2. 以单词长度为步长，遍历目标字符串，如果当前单词在总单词表内，则进入步骤3；反之，则清空当前滑块单词表，将cout置零，将left移动到下一位置
3. 当前滑块档次表中的相应单词计数加1，检查该单词的计数是否小于等于总单词表中该单词的总数，如果是，则将count计数加1，进入步骤5；反之，进入步骤4
4. 根据左起点left收缩滑块，直到收缩到与当前单词相同的字符串片段，将其剔除之后，滑块的收缩工作完成
5. 如果当前count计数等于单词集合长度，记录下left左起点的位置后，将left右移，当前滑块中相应单词计数减1，总计数减1，继续循环

这里解释下步骤4中的收缩滑块，这是因为当前滑块中有单词的出现次数超过了额定的出现次数，那么就是需要收缩滑块来剔除这个单词，相当于是从滑块的左起点开始寻找该单词，找到之后，将该单词的右端点作为滑块新的左起点，这样就保证了滑块中所有单词都是小于等于额定出现次数，这样也保证了count计数的有效性。

遇到总单词表中不存在的单词的情况，在步骤2中已经说明，清空当前数据之后继续循环，也就是保证了滑块中是不会出现不存在单词表中的单词的。

最后，考虑最外圈循环，如果是从0开始作为滑块的初始起点，那么其实并没有遍历字符串中的所有可能子串，因为步长是单词长度，所以移动滑块的时候会跨过很多可能子串，所以要在外圈再加一层循环，这个循环的作用就是移动滑块的初始起点，所以循环次数就是单词的长度。

 

public List<Integer> findSubstring(String S, String[] L) {
    List<Integer> result = new ArrayList<>();
    if (S == null || S.length() == 0 || L == null || L.length == 0)
        return result;
    int strLen = S.length();
    int wordLen = L[0].length();
    Map<String, Integer> map = new HashMap<>();
    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++) {
        Map<String, Integer> curMap = new HashMap<>();
        int count = 0, left = i;
        for (int j = i; j <= strLen - wordLen; j += wordLen) {
            String curStr = S.substring(j, j + wordLen);
            if (map.containsKey(curStr)) {
                if (curMap.containsKey(curStr)) {
                    curMap.put(curStr, curMap.get(curStr) + 1);
                } else {
                    curMap.put(curStr, 1);
                }
                if (curMap.get(curStr) <= map.get(curStr)) {
                    count++;
                } else {
                    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--;
                        }
                    }
                }
                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 {
                curMap.clear();
                count = 0;
                left = j + wordLen;
            }
        }
    }
    return result;
}