LeetCode 30. Substring with Concatenation of All Words

in 应用教程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

题目描述(困难难度)

给定一个字符串 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 中,如果不在的话就更好说了,不在就表明当前子串肯定不符合了,直接判断下个子串就好了。

看一下代码吧

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

时间复杂度:假设 s 的长度是 n,words 里有 m 个单词,那么时间复杂度就是 O(n * m)。

空间复杂度:两个 HashMap,假设 words 里有 m 个单词,就是 O(m)。

解法二

参考 https://leetcode.com/problems...

我们在解法一中,每次移动一个字符。

现在为了方便讨论,我们每次移动一个单词的长度,也就是 3 个字符,这样所有的移动被分成了三类。

以上三类我们以第一类从 0 开始移动为例,讲一下如何对算法进行优化,有三种需要优化的情况。

更多详细通俗题解详见 leetcode.wang
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看