LeetCode 30. Substring with Concatenation of All Words

Problem

30. Substring with Concatenation of All Words

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"]
输出：[]

2. 算法思路

相关问题：

1. 力扣76题

这道题有两种解法，暴力解法和优化版暴力解法（双指针）。跟76题有点像。

暴力解法

第一种就是暴力求解，遍历所有可能的长度为 n * w 的子串(n是单词个数，w为每个单词的长度)，使用hashmap来记录里面每个单词出现的次数，如果和words数组里的单词及出现次数刚好相同，则为一个解，否则继续遍历。这样的话时间复杂度为 o((l - n * w) * (n * w))，共计l - n * w个起始位置，每次遍历长度为 n * w。

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        if (s.length() == 0 || words.length == 0) {
            return new ArrayList<Integer>();
        }
        
        int wordLength = words[0].length();
        int targetLength = wordLength * words.length;
        if (s.length() < targetLength) {
            return new ArrayList<Integer>();
        }
        
        Map<String, Integer> dict = new HashMap();
        // 初始化一个dict，记录一下各个word出现的频率
        for (String word : words) {
            if (!dict.containsKey(word)) {
                dict.put(word, 1);
            } else {
                dict.put(word, dict.get(word) + 1);
            }
        }
        
        List<Integer> res = new ArrayList();
        int start = 0, end = targetLength;
        while (end <= s.length()) {
            if (check(dict, s.substring(start, end), wordLength)) {
                res.add(start);
            }
            start++;
            end++;
        }
        
        return res;
    }
    
    private boolean check(Map<String, Integer> dict, String target, int wordLength) {
        Map<String, Integer> copy = new HashMap();
        copy.putAll(dict);
        
        int start = 0;
        while (start < target.length()) {
            String word = target.substring(start, start + wordLength);
            if (copy.containsKey(word) && copy.get(word) > 0) {
                copy.put(word, copy.get(word) - 1);
            } else {
                return false;
            }
            start += wordLength;
        }
        
        return true;
    }
}

双指针（滑动窗口）

我们需要注意一点，就是每个单词的长度是一致的，也就是说我们可以利用单词长度为w的特性。我们可以将s字符串分为w组，起始位置从0到w-1，以w长度为间隔。以下图为例：

不同颜色就表示不同的分组情况，两个不同颜色之间表示一个单词。然后我们遍历每种颜色的单词的词组，从前到后，使用一个count值来巧妙表示当前有多少合法的单词，如果count值和words里单词数相等，则为一种解。双指针，或者说滑动窗口也可以，判断每个窗口是否符合要求。

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

        int w = words[0].length(), n = words.length, l = s.length(), count = 0;
        Map<String, Integer> total = new HashMap<>(), wd = new HashMap();
        for (String word : words) {
            total.put(word, total.getOrDefault(word, 0) + 1);
        }

        // 共计w中开始位置
        for (int i = 0; i < w; i++) {
            wd.clear();
            count = 0;
            // 每次开始进行遍历，步长为w
            for (int j = i; j + w <= l; j += w) {
                // 注意这里有等于，例如单词长度为5，一个单词的情况，我们第一个单词位置是[0, 4]，大小为5的时候已经是下一个单词了，因此是j >=
                if (j >= i + n * w) {
                    // 此时，从wd里去掉第一个单词
                    String temp = s.substring(j - n * w, j - (n - 1) * w);
                    wd.put(temp, wd.get(temp) - 1);
                    if (wd.get(temp) < total.getOrDefault(temp, 0)) {
                        count--;
                    }
                }

                // 将当前单词插入wd中，如果满足要求，则count++，然后判断。
                String temp = s.substring(j, j + w);
                wd.put(temp, wd.getOrDefault(temp, 0) + 1);
                if (wd.get(temp) <= total.getOrDefault(temp, 0)) {
                    count++;
                }
                if (count == n) {
                    res.add(j - (n - 1) * w);
                }
            }
        }

        return res;
    }
}