Sliding Window - 30. Substring with Concatenation of All Words
Sliding Window - 30. Substring with Concatenation of All Words
30. Substring with Concatenation of All Words
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.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively. The output order does not matter, returning [9,0] is fine too.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: []
思路：
利用一个map，单词作为map的key，value是单词在
words数组中出现的次数。然后去遍历s数组，使用两个指针，一个指针i作为查找单词的起始点，另一个作为单词长度的移动指针，这样在两个指针之间去用另一个哈希表copy来记录相同单词长度的单词和map之间的关系，如果出现map中没有的单词就移动指针i，进行下一轮查找比对。
代码：
java：
class Solution {
/*public List<Integer> findSubstring(String s, String[] words) {
if (s == null || words == null || s.length() == 0 || words.length == 0)
return new ArrayList<>();
List<Integer> res = new ArrayList<>();
int n = words.length, m = words[0].length();
Map<String, Integer> map = new HashMap<>();
// 记录下word中的String的出现次数
for (String str : words) map.put(str, map.getOrDefault(str, 0) + 1);
for (int i = 0; i <= s.length()- n*m; i++) {
HashMap<String, Integer> copy = new HashMap<>(map);
int k = n, j = i;
while(k > 0) {
String str = s.substring(j, j + m);
if (!copy.containsKey(str) || copy.get(str) < 1) break;
copy.put(str, copy.get(str) - 1);
k--;
j += m;
}
if (k == 0) res.add(i);
}
return res;
}*/
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if (s.length() == 0 || words.length == 0 || s.length() < words.length * words[0].length()) {
return res;
}
int wordsLen = words.length, wlen = words[0].length();
Map<String,Integer> map = new HashMap<>();
// 记录word中单词出现的次数
for(String word : words) map.put(word, map.getOrDefault(word, 0) + 1);
// 从单词每一位开始遍历
for (int i = 0; i < wlen; i++) {
// 然后按照单词的长度一个单词一个单词的寻找
for (int j = i; j <= s.length() - wordsLen * wlen; j +=wlen) {
// 寻找匹配的字串
Map<String,Integer> temp = new HashMap<>();
for (int k = wordsLen - 1; k >= 0; k--) {
String t = s.substring(j + k * wlen, j + (k + 1) * wlen);
int val = temp.getOrDefault(t, 0) + 1;
if (val > map.getOrDefault(t, 0)) {
j += k * wlen; // 如果出现map中没有的单词，就直接从下一个窗口起始点开始寻找
break;
}
temp.put(t, val);
if (k == 0) res.add(j);
}
}
}
return res;
}
}```腾讯云开发者
