侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-30. 串联所有单词的子串

阿里灰太狼
2021-12-10 / 0 评论 / 0 点赞 / 245 阅读 / 2,684 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-12-10,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

cj93.pngcj94.png

JAVA解法

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        // 定义一个存储符合要求的起始位置的 list
        List<Integer> res = new ArrayList<>();
        // 定义保存存储传进来的 words 中的所有相同长度的单词的 HashMap
        Map<String, Integer> wordsMap = new HashMap<>();
        if (s.length() == 0 || words.length == 0){
            return res;
        } 
        // 把所有目标单词存进去 wordsMap
        for (String word: words) {
            // 主串 s 中没有这个单词,直接返回空
            if (s.indexOf(word) < 0){
                return res;
            } 
            // map 中保存每个单词,和它出现的次数
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }
        // 每个单词的长度,和总长度
        int oneLen = words[0].length(), wordsLen = oneLen * words.length;
        // 主串 s 长度小于单词总和,返回空
        if (wordsLen > s.length()){
            return res;
        }        
        /**
            只讨论从 0,1,..., oneLen - 1 开始的子串情况,每次进行匹配的窗口
              大小为 wordsLen,每次后移一个单词长度,由左右窗口维持当前窗口位置。
         */
        for (int i = 0; i < oneLen; ++i) {
            // 左右窗口
            int left = i, right = i, count = 0;
            // 统计每个符合要求的 word
            Map<String, Integer> subMap = new HashMap<>();
            // 右窗口不能超出主串长度
            while (right + oneLen <= s.length()) {
                // 得到一个单词
                String word = s.substring(right, right + oneLen);
                // 右窗口右移
                right += oneLen;
                // words[] 中没有这个单词,那么当前窗口肯定匹配失败,直接右移到这个单词后面
                if (!wordsMap.containsKey(word)) {
                    left = right;
                    // 窗口内单词统计 map 清空,重新统计
                    subMap.clear();
                    // 符合要求的单词数清 0
                    count = 0;
                } else {
                    // 统计当前子串中这个单词出现的次数
                    subMap.put(word, subMap.getOrDefault(word, 0) + 1);
                    ++count;
                    /**
                        如果这个单词出现的次数大于 words[] 中它对应的次数,
                          又由于每次匹配和 words 长度相等的子串,
                          如 ["foo","bar","foo","the"]  "| foobarfoobar| foothe",
                          第二个bar虽然是 words[] 中的单词,但是次数超了,
                          那么右移一个单词长度后 "|barfoobarfoo|the",
                          bar 还是不符合,所以直接从这个不符合的bar之后开始匹配,
                          也就是将这个不符合的 bar 和它之前的单词(串)全移出去
                     */ 
                    while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
                        // 从当前窗口字符统计 map 中删除从左窗口开始到数量超限的单词并且对应记录次数减一                   
                        String w = s.substring(left, left + oneLen);
                        subMap.put(w, subMap.getOrDefault(w, 0) - 1);
                        // 符合的单词数减一
                        --count;
                        // 左窗口位置右移
                        left += oneLen;
                    }
                    // 当前窗口字符串满足要求
                    if (count == words.length){
                        res.add(left);
                    } 
                }
            }
        }
        return res;
    }
}

题解分析

这道题用的是滑动窗口算法。首先,定义一个存储符合要求的起始位置的 list,定义保存存储传进来的 words 中的所有相同长度的单词的 HashMap,接着遍历传进来的 words 把所有目标单词存进去 wordsMap,map 中保存每个单词,和它出现的次数。获取每个单词的长度,和总长度。

最外层只讨论从 0,1,..., oneLen - 1 开始的子串情况,每次进行匹配的窗口,大小为 wordsLen,每次后移一个单词长度,由左右窗口维持当前窗口位置。定义左右窗口,统计每个符合要求的 word,并且右窗口不能超出主串长度。进入
while 循环,每得到一个单词,右窗口右移,若 words[] 中没有这个单词,那么当前窗口肯定匹配失败,直接右移到这个单词后面,则窗口内单词统计 map 清空,重新统计符合要求的单词数清 0。若 words[] 中有这个单词,则统计当前子串中这个单词出现的次数。

如果这个单词出现的次数大于 words[] 中它对应的次数,又由于每次匹配和 words 长度相等的子串,如 ["foo","bar","foo","the"] "| foobarfoobar| foothe",第二个bar虽然是 words[] 中的单词,但是次数超了,那么右移一个单词长度后 "|barfoobarfoo|the", bar 还是不符合,所以直接从这个不符合的bar之后开始匹配,也就是将这个不符合的 bar 和它之前的单词(串)全移出去。

若 subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0) 即单词存在但次数超了,从当前窗口字符统计 map 中删除从左窗口开始到数量超限的单词并且对应记录次数减一,左窗口位置右移,并判断当前窗口字符串满足要求;若不存在次数超了的情况,则直接进入判断当前窗口字符串满足要求,若满足则 count++,若不满足则跳过判断继续到最近的 while 循环,直到整个 s 都匹配完则跳出 while 到最外层的 for 向右移动窗口,然后继续上述过程,直到最外层的 for 也遍历完整个 s 字符串,最终返回储存 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置的 res 数组。

leetcode原题: 30. 串联所有单词的子串

0

评论区