力扣经典150题第三十二题：串联所有单词的子串

用户8589624

发布于 2025-11-13 15:55:32

380

文章被收录于专栏：nginxnginx

解题思路与实现 - 串联所有单词的子串

问题描述

给定一个字符串 s 和一个字符串数组 words，数组中所有字符串长度相同。s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。找出所有串联子串在 s 中的起始索引。

示例

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”] 输出：[0,9] 解释：子串 “barfoo” 和 “foobar” 都是以 ["foo","bar"] 顺序排列的连接。
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”] 输出：[] 解释：无符合条件的串联子串。
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”] 输出：[6,9,12] 解释：子串 “foobarthe”、“barthefoo” 和 “thefoobar” 都是以 ["bar","foo","the"] 顺序排列的连接。

解题思路

使用滑动窗口（双指针）和哈希表的方法解决该问题：

将 words 中的所有单词存入哈希表 wordCount，记录每个单词的出现次数。
遍历字符串 s，以每个可能的起始位置作为窗口的起点，通过滑动窗口判断是否能匹配所有单词。
窗口的大小应为 words 中所有单词的总长度。
滑动窗口每次向右移动一个单词长度，维护一个窗口中包含的单词计数 currentWords。
若窗口中的单词与 words 中的单词匹配，则将起点加入结果列表。

算法实现

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    if (s == null || s.isEmpty() || words == null || words.length == 0) {
        return result;
    }
    
    Map<String, Integer> wordCount = new HashMap<>();
    int wordLength = words[0].length();
    int totalLength = wordLength * words.length;
    
    for (String word : words) {
        wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
    }
    
    for (int i = 0; i <= s.length() - totalLength; i++) {
        Map<String, Integer> currentWords = new HashMap<>();
        int j = 0;
        
        while (j < words.length) {
            String currentWord = s.substring(i + j * wordLength, i + (j + 1) * wordLength);
            if (!wordCount.containsKey(currentWord)) {
                break;
            }
            currentWords.put(currentWord, currentWords.getOrDefault(currentWord, 0) + 1);
            if (currentWords.get(currentWord) > wordCount.getOrDefault(currentWord, 0)) {
                break;
            }
            j++;
        }
        
        if (j == words.length) {
            result.add(i);
        }
    }
    
    return result;
}