題目

給定一個字串 s 和一個單字陣列 words，所有單字的長度相同。
要求找出 s 中所有包含 words 任意排列組合連接的子字串的起始索引，並回傳這些索引（順序不限）。

例如：
如果 words = ["ab","cd","ef"]，則 "abcdef", "abefcd", "cdabef" 等都是合法連接字串。

範例

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: 索引 0 和 9 的子字串分別是 "barfoo" 和 "foobar"，都符合條件。

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

解題思路

這題本質上是 滑動窗口 + HashMap 計數 問題。
主要思路：

每個單字長度固定，窗口大小為 wordLength × words.length。

用 HashMap 儲存 words 的計數。

對每個可能的起始位置，用滑動窗口檢查該窗口是否包含所有 words。

每次窗口移動時更新計數，避免重複計算。

時間複雜度：O(N × wordLength)，空間複雜度：O(M)，其中 N 為字串長度，M 為 words 陣列大小。

Java 實作
import java.util.*;

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

    int wordLength = words[0].length();
    int wordCount = words.length;
    int windowLength = wordLength * wordCount;

    Map<String, Integer> wordMap = new HashMap<>();
    for (String word : words) {
        wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
    }

    for (int i = 0; i < wordLength; i++) {
        int left = i, count = 0;
        Map<String, Integer> windowMap = new HashMap<>();

        for (int right = i; right <= s.length() - wordLength; right += wordLength) {
            String word = s.substring(right, right + wordLength);
            if (wordMap.containsKey(word)) {
                windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);
                count++;

                while (windowMap.get(word) > wordMap.get(word)) {
                    String leftWord = s.substring(left, left + wordLength);
                    windowMap.put(leftWord, windowMap.get(leftWord) - 1);
                    left += wordLength;
                    count--;
                }

                if (count == wordCount) {
                    result.add(left);
                    String leftWord = s.substring(left, left + wordLength);
                    windowMap.put(leftWord, windowMap.get(leftWord) - 1);
                    left += wordLength;
                    count--;
                }
            } else {
                windowMap.clear();
                count = 0;
                left = right + wordLength;
            }
        }
    }

    return result;
}

}

心得

這題感覺很像在做 文字搜尋遊戲，滑動窗口的技巧是核心。
一開始很容易想到暴力解法，但會超時；用 HashMap 優化後，時間複雜度大大下降。
另外，處理不同起始點（0 ~ wordLength-1）是必須的，否則會漏掉有效組合。
這讓我更熟悉 字符串處理 + HashMap 計數 + 窗口滑動 的經典技巧。