首页 > 代码库 > LeetCode: Substring with Concatenation of All Words 解题报告
LeetCode: Substring with Concatenation of All Words 解题报告
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).
SOLUTION 1:
1. 使用HashMap来保存L中所有的字串。
2. 暴力破解之。使用i记录我们的查找结果字符串的位置，j记录单个单词的查找位置。j每次移动一个L中单词的位置。
3. 注意各种越界条件：i查到离结束还有L*N（L中所有单词总长）的时候，即需要停止。
j 也要考虑每一次查找的单词的长度。
4. 使用第二个HashMap来记录我们查到的单词。如果所有的单词都查到了，即可记录一个解。
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.length28 // 这里很关键，如果长度不够了，不需要再继续查找 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 }
SOLUTION 2:
1. 与解1相比，我们这次每次复制一个HashMap，找到一个单词，即减少此单词的计数，直到HashMap为空，表示我们找到一个解。
与Solution 1相比，这个方法写起来会简单一点。
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.length23 // 这里很关键，如果长度不够了，不需要再继续查找 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 }
SOLUTION 3:
九章算法官网解：
http://www.ninechapter.com/solutions/substring-with-concatenation-of-all-words/
主页君GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/FindSubstring.java
LeetCode: Substring with Concatenation of All Words 解题报告