30 串联所有单词的子串

🚀 相关链接

LeetCode 30 - 串联所有单词的子串

📜 描述

给定一个字符串 s 和一个字符串数组 words。words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

💡 示例

示例 1

• 输入: s = "barfoothefoobarman", words = ["foo","bar"]
• 输出: [0,9]
• 解释:
  • 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
  • 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。

示例 2

• 输入: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
• 输出: []
• 解释: 没有符合条件的子串。

示例 3

• 输入: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
• 输出: [6,9,12]
• 解释:
  • 子串 "foobarthe" 开始位置是 6。
  • 子串 "barthefoo" 开始位置是 9。
  • 子串 "thefoobar" 开始位置是 12。

📝 提示

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

💭 思路

方法一：滑动窗口 + 哈希表

1. 预处理：

   • 计算每个单词的长度 wordLen 和所有单词连接后的总长度 groupLen。
   • 如果 s 的长度小于 groupLen，直接返回空列表。

2. 滑动窗口：

   • 使用滑动窗口在 s 上滑动，窗口大小为 groupLen。
   • 对于每个窗口，统计窗口内单词出现的频率，并与 words 的频率进行比较。
   • 具体实现为使用一个哈希表，key为单词，用words数组进行初始化，words数组每出现一次就减1，窗口内出现一次就加1，若该窗口使hashmap中的值全为0，则该窗口起始位置为1个答案。

💻 代码实现

public List<Integer> findSubstring(String s, String[] words) {
    int wordLen = words[0].length();
    int groupLen = wordLen * words.length;
    if (s.length() < groupLen) {
        return Collections.emptyList();
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < wordLen; i++) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            int val = map.getOrDefault(word, 0);
            map.put(word, val - 1);
        }
        int left = i, r = left + groupLen - 1;
        while (r < s.length()) {
            String subStr = s.substring(left, r + 1);
            if (left == i) {
                for (int j = 0; j < subStr.length(); j += wordLen) {
                    String word = subStr.substring(j, j + wordLen);
                    if (map.containsKey(word)) {
                        map.put(word, map.get(word) + 1);
                    }
                }
            } else {
                String formerWord = s.substring(left - wordLen, left);
                String newWord = s.substring(left + groupLen - wordLen, left + groupLen);
                if (map.containsKey(formerWord)) {
                    map.put(formerWord, map.get(formerWord) - 1);
                }
                if (map.containsKey(newWord)) {
                    map.put(newWord, map.get(newWord) + 1);
                }
            }
            if (map.values().stream().allMatch(v -> v == 0)) {
                ans.add(left);
            }
            left += wordLen;
            r = left + groupLen - 1;
        }
    }
    return ans;
}