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: []
思路1
- 遍历所有可能的字串
- 判断字串每个单词是否在单词集合中，以及单词出现的次数不能超过集合中单词出现的次数
- 如果全部满足，则是一个局部解
Java 实现
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int wordNum = words.length;
if (wordNum == 0) {
return res;
}
int wordLen = words[0].length();
//HashMap1 存所有单词 可能有重复的单词
HashMap<String, Integer> allWords = new HashMap<String, Integer>();
for (String w : words) {
int value = allWords.getOrDefault(w, 0);
allWords.put(w, value + 1);
}
//遍历所有子串
for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
//HashMap2 存当前扫描的字符串含有的单词
HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
int num = 0;
//判断该子串是否符合
while (num < wordNum) {
// 取出当前的单词
String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
// 判断该单词在 HashMap1 中，什么次序不重要
if (allWords.containsKey(word)) {
int value = hasWords.getOrDefault(word, 0);
hasWords.put(word, value + 1);
//判断当前单词的 value 和 HashMap1 中该单词的 value，出现的次数要小于等于总的集合
if (hasWords.get(word) > allWords.get(word)) {
break;
}
} else {
break;
}
num++;
}
//判断是不是所有的单词都符合条件
if (num == wordNum) {
res.add(i);
}
}
return res;
}
}
思路2
- 优化前进速度，每次走一个单词的长度
- 优化字串搜索的过程，发现超次数后，进行移除，更新已匹配的字串
Java 代码
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int wordNum = words.length;
if (wordNum == 0) {
return res;
}
int wordLen = words[0].length();
HashMap<String, Integer> allWords = new HashMap<String, Integer>();
for (String w : words) {
int value = allWords.getOrDefault(w, 0);
allWords.put(w, value + 1);
}
//将所有移动分成 wordLen 类情况
for (int j = 0; j < wordLen; j++) {
HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
int num = 0; //记录当前 HashMap2（这里的 hasWords 变量）中有多少个单词
//每次移动一个单词长度
for (int i = j; i < s.length() - wordNum * wordLen + 1; i = i + wordLen) {
boolean hasRemoved = false; //防止情况三移除后，情况一继续移除
while (num < wordNum) {
String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
if (allWords.containsKey(word)) {
int value = hasWords.getOrDefault(word, 0);
hasWords.put(word, value + 1);
//出现情况三，遇到了符合的单词，但是次数超了
if (hasWords.get(word) > allWords.get(word)) {
// hasWords.put(word, value);
hasRemoved = true;
int removeNum = 0;
// 一直移除单词，直到次数符合了
while (hasWords.get(word) > allWords.get(word)) {
String firstWord = s.substring(i + removeNum * wordLen, i + (removeNum + 1) * wordLen);
int v = hasWords.get(firstWord);
hasWords.put(firstWord, v - 1);
removeNum++;
}
num = num - removeNum + 1; //加 1 是因为我们把当前单词加入到了 HashMap 2 中，剩余已匹配的单词数量
i = i + (removeNum - 1) * wordLen; //这里依旧是考虑到了最外层的 for 循环，看情况二的解释 更新已匹配位置
break;
}
//出现情况二，遇到了不匹配的单词，直接将 i 移动到该单词的后边（但其实这里
//只是移动到了出现问题单词的地方，因为最外层有 for 循环， i 还会移动一个单词
//然后刚好就移动到了单词后边）
} else {
hasWords.clear();// 清除单词
i = i + num * wordLen;
num = 0;
break;
}
num++;
}
if (num == wordNum) {
res.add(i);
}
//出现情况一，子串完全匹配，我们将上一个子串的第一个单词从 HashMap2 中移除
if (num > 0 && !hasRemoved) {
String firstWord = s.substring(i, i + wordLen);
int v = hasWords.get(firstWord);
hasWords.put(firstWord, v - 1);
num = num - 1;
}
}
}
return res;
}
<!-- 作者：windliang
链接：https://leetcode-cn.com/problems/two-sum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 -->
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
