题目描述

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

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

样例

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

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

算法分析

• 1、先用map哈希表将word中的单词存起来，每个单词有多少个
• 2、find哈希表表示当从i开始长度是n * len的滑动窗口中将该窗口的字符串以长度是len进行分割出来记录元素的哈希表，记录该窗口每个单词有多少个
• 3、当枚举到某个窗口时，枚举该窗口的某个单词
  • 如果map哈希表中存在该单词，则在find哈希表中记录该单词的数量，并且始终保持find.get(t) <= map.get(t)的状态
  • 如果map哈希表中不存在该单词，则一定不符合条件
• 4、最后，如果该窗口的所有单词都枚举完，没有发现错误，则表示从i开始的窗口符合条件

时间复杂度

Java 代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<Integer>();
        if(words.length == 0) return ans;

        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(String word : words)
        {
            map.put(word,map.getOrDefault(word,0) + 1);
        }
        int n = words.length;
        int len = words[0].length();
        //当前窗口的的哈希表
        HashMap<String, Integer> find = new HashMap<String, Integer>();
        for(int i = 0;i <= s.length() - n * len;i ++)
        {
            find.clear();
            int j = 0;
            for(;j < n;j ++)
            {
                String t = s.substring(i + j * len,i + j * len + len);
                if(map.containsKey(t))
                {
                    find.put(t,find.getOrDefault(t,0) + 1);
                    if(find.get(t) > map.get(t)) break;
                }
                else break;
            }
            if(j == n) ans.add(i);
        }
        return ans;
    }
}