leetcode第30题

2022-09-25 93

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 如上图，利用循环变量 i ，依次后移，判断每个子串是否符合即可。怎么判断子串是否符合？这也是这个题的难点了，由于子串包含的单词顺序并不需要固定，如果是两个单词 A，B，我们只需要判断子串是否是 AB 或者 BA 即可。如果是三个单词 A，B，C 也还好，只需要判断子串是否是 ABC，或者 ACB，BAC，BCA，CAB，CBA 就可以了，但如果更多单词呢？那就崩溃了。链接)的作者提出了，用两个 HashMap 来解决。首先，我们把所有的单词存到 HashMap 里，key 直接存单词，value 存单词出现的个数（因为给出的单词可能会有重复的，所以可能是 1 或 2 或者其他）。然后扫描子

给定一个字符串 s ，给定 n 个单词 word，找出所有子串的开始下标，使得子串包含了给定的所有单词，顺序可以不对应。如果有重复的单词，比如有 [ " foo " , " foo " ] 那么子串也必须含有两个 " foo "，也就是说个数必须相同。

解法一

参考 leetCode 里的 solution)

首先，最直接的思路，判断每个子串是否符合，符合就把下标保存起来，最后返回即可。

如上图，利用循环变量 i ，依次后移，判断每个子串是否符合即可。

怎么判断子串是否符合？这也是这个题的难点了，由于子串包含的单词顺序并不需要固定，如果是两个单词 A，B，我们只需要判断子串是否是 AB 或者 BA 即可。如果是三个单词 A，B，C 也还好，只需要判断子串是否是 ABC，或者 ACB，BAC，BCA，CAB，CBA 就可以了，但如果更多单词呢？那就崩溃了。

链接)的作者提出了，用两个 HashMap 来解决。首先，我们把所有的单词存到 HashMap 里，key 直接存单词，value 存单词出现的个数（因为给出的单词可能会有重复的，所以可能是 1 或 2 或者其他）。然后扫描子串的单词，如果当前扫描的单词在之前的 HashMap 中，就把该单词存到新的 HashMap 中，并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ，如果大了，就代表该子串不是我们要找的，接着判断下一个子串就可以了。如果不大于，那么我们接着判断下一个单词的情况。子串扫描结束，如果子串的全部单词都符合，那么该子串就是我们找的其中一个。看下具体的例子。我们把 words 存到一个 HashMap 中。

然后遍历子串的每个单词。

第一个单词在 HashMap1 中，然后我们把 foo 存到 HashMap2 中。并且比较此时 foo 的 value 和 HashMap1 中 foo 的 value，1 < 2，所以我们继续扫描。

第二个单词也在 HashMap1 中，然后把 foo 存到 HashMap2 中，因为之前已经存过了，所以更新它的 value 为 2 ，然后继续比较此时 foo 的 value 和 HashMap1 中 foo 的 value，2 <= 2，所以继续扫描下一个单词。

第三个单词也在 HashMap1 中，然后把 foo 存到 HashMap2 中，因为之前已经存过了，所以更新它的 value 为 3，然后继续比较此时 foo 的 value 和 HashMap1 中 foo 的 value，3 > 2，所以表明该字符串不符合。然后判断下个子串就好了。

当然上边的情况都是单词在 HashMap1 中，如果不在的话就更好说了，不在就表明当前子串肯定不符合了，直接判断下个子串就好了。

看一下代码吧

publicList<Integer>findSubstring(Strings, String[] words) {
List<Integer>res=newArrayList<Integer>();
intwordNum=words.length;
if (wordNum==0) {
returnres;
    }
intwordLen=words[0].length();
//HashMap1 存所有单词HashMap<String, Integer>allWords=newHashMap<String, Integer>();
for (Stringw : words) {
intvalue=allWords.getOrDefault(w, 0);
allWords.put(w, value+1);
    }
//遍历所有子串for (inti=0; i<s.length() -wordNum*wordLen+1; i++) {
//HashMap2 存当前扫描的字符串含有的单词HashMap<String, Integer>hasWords=newHashMap<String, Integer>();
intnum=0;
//判断该子串是否符合while (num<wordNum) {
Stringword=s.substring(i+num*wordLen, i+ (num+1) *wordLen);
//判断该单词在 HashMap1 中if (allWords.containsKey(word)) {
intvalue=hasWords.getOrDefault(word, 0);
hasWords.put(word, value+1);
//判断当前单词的 value 和 HashMap1 中该单词的 valueif (hasWords.get(word) >allWords.get(word)) {
break;
                }
            } else {
break;
            }
num++;
        }
//判断是不是所有的单词都符合条件if (num==wordNum) {
res.add(i);
        }
    }
returnres;
}