30. 串联所有单词的子串
自己解法
字符串匹配的问题，因为第4题已经遇到过使用Map去保存出现的位置，所以第一想法，想到了使用map保存所有word在s中出现的下标index，然后合并直接看能不能连起来，结果发现这种不分辨word是否出现过，只按下标能不能连起来，是错误的，可能有符合条件的一个出现多次。按word出现的下标分别连接，也会有问题，出现了多个列表归并的问题，很复杂，可见自己的思路是有点问题的。
新方法为，设置两个map，一个map存words里面字符串出现的次数，一个map存遍历s,遇到的words中字符串的个数，两者一致时，记录下标。中间如果遇到不满足的情况，清空第二个统计的map，重新开始。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if (s.equals("") || words.length == 0) {
return res;
}
Map<String, Integer> wordMap = new HashMap<>();
Map<String, Integer> statMap = new HashMap<>();
List<String> wordList = Arrays.asList(words);
for (String word : wordList) {
wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
}
int wordLen = words[0].length();
for (int i = 0; i < s.length(); i++) {
int j = i;
while (j + wordLen <= s.length()) {
String temp = s.substring(j, j + wordLen);
if (!wordList.contains(temp)) {
statMap = new HashMap<>();
break;
}
int times = statMap.getOrDefault(temp, 0) + 1;
if (times <= wordMap.get(temp)) {
statMap.put(temp, times);
if (isMapEqual(wordMap, statMap)) {
res.add(j - wordLen * (wordList.size() - 1));
statMap = new HashMap<>();
break;
}
j = j + wordLen;
} else {
// 有多余的字符串，说明不符合，直接清空统计
statMap = new HashMap<>();
break;
}
}
statMap = new HashMap<>();
}
return res;
}
private boolean isMapEqual(Map<String, Integer> wordMap, Map<String, Integer> statMap) {
for (Map.Entry<String, Integer> entry : wordMap.entrySet()) {
if (!entry.getValue().equals(statMap.get(entry.getKey()))) {
return false;
}
}
return true;
}
}
大神解法
先贴个思路和自己差不多的，但写法更简洁的解法
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;
}
还有一种分3种情况不同后移的解法，每次遍历，分别从wordLen的范围内不同下标开始，保证所有的情况都能遍历到，然后后移的时候就不用逐个后移了，可以每次移动wordLen了。
第一种情况：完全匹配的情况下，去掉首个字符串，接着往里添加后面字符串，看能否满足，不清空统计map，开始位置也直接从后面开始。
第二种情况：当前字符串不在查找字符串中，直接从当前字符串后面开始查找，清空统计map。
第三种情况：当前字符串过多，从起始位置进行移除，直到当前字符串不多为止。
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;
}
