LeetCode: Substring with Concatenation of All Words 解题报告

 1 // SOLUTION 1:
 2     public List<Integer> findSubstring1(String S, String[] L) {
 3         HashMap<String, Integer> map = new HashMap<String, Integer>();
 4         HashMap<String, Integer> found = new HashMap<String, Integer>();
 5         List<Integer> ret = new ArrayList<Integer>();
 6         
 7         if (S == null || L == null || L.length == 0) {
 8             return ret;
 9         }
10         
11         int cntL = 0;
12         
13         // put all the strings into the map.
14         for (String s: L) {
15             if (map.containsKey(s)) {
16                 map.put(s, map.get(s) + 1);
17             } else {
18                 map.put(s, 1);
19                 cntL++;
20             }
21         }
22         
23         int lenL = L[0].length();
24         
25         int cntFound = 0;
26         
27         // 注意这里的条件：i < S.length() - lenL * L.length
28         // 这里很关键，如果长度不够了，不需要再继续查找 
29         for (int i = 0; i <= S.length() - lenL * L.length; i++) {
30             // clear the found hashmap.
31             found.clear();
32             cntFound = 0;
33             
34             // 一次前进一个L的length.
35             // 注意j <= S.length() - lenL; 防止越界
36             for (int j = i; j <= S.length() - lenL; j += lenL) {
37                 String sub = S.substring(j, j + lenL);
38                 if (map.containsKey(sub)) {
39                     if (found.containsKey(sub)) {
40                         if (found.get(sub) == map.get(sub)) {
41                             // 超过了限制数目
42                             break;
43                         }
44                         
45                         found.put(sub, found.get(sub) + 1);
46                     } else {
47                         found.put(sub, 1);
48                     }
49                     
50                     if (found.get(sub) == map.get(sub)) {
51                         cntFound++;
52                     }
53                     
54                     // L中所有的字符串都已经找到了。
55                     if (cntFound == cntL) {
56                         ret.add(i);
57                     }
58                 } else {
59                     // 不符合条件，可以break,i前进到下一个匹配位置
60                     break;
61                 }
62             }
63         }
64         
65         return ret;
66     }

 1 // SOLUTION 2:
 2     public List<Integer> findSubstring(String S, String[] L) {
 3         HashMap<String, Integer> map = new HashMap<String, Integer>();
 4         HashMap<String, Integer> found;
 5         List<Integer> ret = new ArrayList<Integer>();
 6         
 7         if (S == null || L == null || L.length == 0) {
 8             return ret;
 9         }
10         
11         // put all the strings into the map.
12         for (String s: L) {
13             if (map.containsKey(s)) {
14                 map.put(s, map.get(s) + 1);
15             } else {
16                 map.put(s, 1);
17             }
18         }
19         
20         int lenL = L[0].length();
21         
22         // 注意这里的条件：i < S.length() - lenL * L.length
23         // 这里很关键，如果长度不够了，不需要再继续查找 
24         for (int i = 0; i <= S.length() - lenL * L.length; i++) {
25             // 每一次，都复制之前的hashMap.
26             found = new HashMap<String, Integer>(map);
27             
28             // 一次前进一个L的length.
29             // 注意j <= S.length() - lenL; 防止越界
30             for (int j = i; j <= S.length() - lenL; j += lenL) {
31                 String sub = S.substring(j, j + lenL);
32                 if (found.containsKey(sub)) {
33                     // 将找到字符串的计数器减1.
34                     found.put(sub, found.get(sub) - 1);
35                     
36                     // 减到0即可将其移出。否则会产生重复运算，以及我们用MAP为空来判断是否找到所有的单词。
37                     if (found.get(sub) == 0) {
38                         found.remove(sub);
39                     }
40                 } else {
41                     // 不符合条件，可以break,i前进到下一个匹配位置
42                     break;
43                 }
44                 
45                 // L中所有的字符串都已经找到了。
46                 if (found.isEmpty()) {
47                     ret.add(i);
48                 }
49             }
50         }
51         
52         return ret;
53     }