leetcode|困难:30. 串联所有单词的子串

jupiter
2022-04-26 / 0 评论 / 678 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年04月26日,已超过781天没有更新,若内容或图片失效,请留言反馈。

leetcode|困难:30. 串联所有单词的子串

1.题目

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。

示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]

提示:

  • 1 <= s.length <= 104
  • s 由小写英文字母组成
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] 由小写英文字母组成

2. 题解

2.1 思路分析

思路1:滑动窗口+词频统计
    对words进行词频统计 
    然后以words包含的所有字符数作为窗口大小进行滑动+窗口词频统计
    判断词频是否相等并记录相对的位置
思路2:#TODO
    借鉴KMP对思路1进行优化 避免进行一些冗余比较

2.2 代码实现

  • 思路1:滑动窗口+词频统计
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();

        // 记录下来每个单词的长度和单词的总长度
        int wordLen = words[0].length();
        int allWordLen = words.length*wordLen;

        // 统计words的词频
        Map<String,Integer> wordFrequnce = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if(!wordFrequnce.containsKey(words[i])) {
                wordFrequnce.put(words[i], 1);
            }else {
                wordFrequnce.replace(words[i], wordFrequnce.get(words[i])+1);
            }
        }

        // 采用滑动窗口进行遍历,每次滑动一个字符
        for (int i = 0; i <= s.length()-allWordLen; i++) {
            // 统计滑动窗口内的词频
            Map<String,Integer> winWordFrequnce = new HashMap<>();
            for (int j = 0; j < allWordLen; j+=wordLen) {
                String tmpWord = s.substring(i+j,i+j+wordLen);
                if(!winWordFrequnce.containsKey(tmpWord)) {
                    winWordFrequnce.put(tmpWord, 1);
                }else {
                    winWordFrequnce.replace(tmpWord, winWordFrequnce.get(tmpWord)+1);
                }
            }
            // 判断二者的词频是否一致
            boolean sameFlag = winWordFrequnce.equals(wordFrequnce);

            // 将开始所以加入到res
            if(sameFlag){
                res.add(i);
            }
        }
        return res;
    }
}

2.3 提交结果

提交结果执行用时内存消耗语言提交时间备注
通过247 ms42.2 MBJava2022/04/26 13:56添加备注

参考资料

  1. https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
0

评论 (0)

打卡
取消