LeetCode30 串联所有单词的子串

hashmap何时使用

在涉及字符串S是否在字符串P中被包含，或者寻找特定字符，只要是找值，或者是要求是否符合某个特征，都可以用hashmap。 那么本题利用hashmap更是一种巧妙地方法。算法如下： 创建两个hashmap，一个存储单词，一个存储模式串中子串中单词出现个数。 将所有单词放到hashmap1中,并记录所有单词出现的次数。 接下来对子串进行扫描： 如果字串不出现在hashmap1中，则跳过进行下一轮循环， 如果在hashmap1中，放到hashmap2中，如果hashmap2与hashmap1中存放的内容一致时，即可满足答案。

本题注意单词长度相同。

解法一：

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; }

解法二：

解法二是对解法一的优化，因为解法一每次只是移动一个字符，浪费效率， 所以解法二每次移动单词长度个字符。 但是要分情况进行讨论： 请参考以下文章： https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-6/ 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; }