leetcode-substring-with-concatenation-of-all-words

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/substring-with-concatenation-of-all-words/

　　给你一个字符串s和字符串数组words，输出字符串数组words中的字符串的任意组合形成的字符串在s中的index的list。

题目分析

　　最开始用暴力方法做，发现超时，最后参考了这篇文章的做法，利用了滑动窗口的做法进行优化，是用HashMap维护了一个words[0].length的窗口。

代码

　　暴力超时的解法，时间复杂度：O(s.length words.length words[0].length)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<Integer>();
        if (s.length() == 0 || words.length == 0 || words[0].length() == 0) {
            return ans;
        }
        int lenS = s.length();
        int n = words.length;
        int m = words[0].length();
        Map<String, Integer> wordCount = new HashMap<String, Integer>();
        for (String w : words) {
            if (wordCount.containsKey(w)) {
                wordCount.put(w, wordCount.get(w) + 1);
            } else {
                wordCount.put(w, 1);
            }
        }
        for (int i = 0; i <= lenS - n * m; i++) {
            Map<String, Integer> exist = new HashMap<String, Integer>();
            int j = 0;
            for (; j <= (n * m - m); j += m) {
                String str = s.substring(i + j, i + j + m);
                if (!wordCount.containsKey(str)) {
                    break;
                }
                if (!exist.containsKey(str)) {
                    exist.put(str, 1);
                } else {
                    if (exist.get(str) + 1 > wordCount.get(str)) {
                        break;
                    } else {
                        exist.put(str, exist.get(str) + 1);
                    }
                }
            }
            if (j > (n * m - m)) {
                ans.add(i);
            }
        }
        return ans;
    }
}

　　利用滑动窗口，AC代码，时间复杂度：O(s.length * words[0].length) ，因为从jdk7 update6开始substring()方法的时间复杂度不是O(1)了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<Integer>();
        if (s.length() == 0 || words.length == 0 || words[0].length() == 0) {
            return ans;
        }
        Map<String, Integer> hash = new HashMap<String, Integer>();
        for (String w : words) {
            if (hash.containsKey(w)) {
                hash.put(w, hash.get(w) + 1);
            } else {
                hash.put(w, 1);
            }
        }
        int wSize = words[0].length();
        for (int start = 0; start < wSize; start++) {
            int wCount = 0;
            Map<String, Integer> window = new HashMap<String, Integer>();
            for (int i = start; i + wSize <= s.length(); i += wSize) {
                String word = s.substring(i, i + wSize);
                if (!hash.containsKey(word)) {
                    window.clear();
                    wCount = 0;
                } else {
                    wCount++;
                    if (window.containsKey(word)) {
                        window.put(word, window.get(word) + 1);
                    } else {
                        window.put(word, 1);
                    }
                    while (window.get(word) > hash.get(word)) {
                        String removeWord = s.substring(i - (wCount - 1) * wSize, i - (wCount - 1) * wSize + wSize);
                        window.put(removeWord, window.get(removeWord) - 1);
                        wCount--;
                    }
                }
                
                if (wCount == words.length) {
                    ans.add(i - (wCount - 1) * wSize);
                }
            }
        }
        return ans;
    }
}