題目描述

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
給定一個(gè)String s和一個(gè)單詞的數(shù)組words上渴，數(shù)組里面的單詞長度相等榛瓮，從s中找出字符串缝呕，使得數(shù)組中的每個(gè)單詞剛好都出現(xiàn)過一次，也就是字符串是數(shù)組中單詞的一個(gè)全排列撞秋。

Example
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

思路分析

注意題目中的條件绸硕，words數(shù)組中的單詞長度相等琼讽，如果沒有這個(gè)條件這道題還挺復(fù)雜的徘熔。如果長度相等的話形如barfoofoothefoobarman的字符串就可以被三等分

• bar foo foo the foo bar man
• b arf oof oot hef oob arm an
• ba rfo ofo oth efo oba rma n

三個(gè)為一組進(jìn)行分組，總共三種可能的分組霉猛。同時(shí)注意條件尺锚，words數(shù)組中的單詞可以重復(fù)，會出現(xiàn)["foo","bar","foo"]的情況惜浅，這種情況也需要匹配到兩個(gè)foo瘫辩，即foobarfoo這樣的子串。
因此需要先用一個(gè)Map wordMap來記錄下words數(shù)組中每個(gè)單詞的次數(shù)赡矢，例如本例中就是
bar: 1
foo: 1
然后分別對以上三種分組方式進(jìn)行分析杭朱，遍歷采用left和right兩個(gè)指針，對s中的每個(gè)單詞和words數(shù)組中的進(jìn)行匹配吹散，同時(shí)用tempMap記錄當(dāng)前l(fā)eft和right指針之間的各個(gè)單詞的數(shù)量（用來和wordMap比較）弧械。
算法的執(zhí)行過程如圖。

算法執(zhí)行邏輯

代碼實(shí)現(xiàn)

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
               List<Integer> result = new ArrayList<>();
        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            if (wordMap.containsKey(word)) {
                wordMap.put(word, wordMap.get(word) + 1);
            } else {
                wordMap.put(word, 1);
            }
        }

        if (s.length() == 0 || words.length == 0) {
            return result;
        }

        int wordLen = words[0].length();
        int totalLen = wordLen * words.length;

        for (int i = 0; i < words[0].length(); i++) {
            int left = i;
            int right = i;
            Map<String, Integer> tempMap = new HashMap<>();
            while (right + wordLen <= s.length()) {
                // 滑窗右側(cè)擴(kuò)張
                String temp = s.substring(right, right + wordLen);
                right += wordLen;
                if (wordMap.containsKey(temp)) {
                    if (tempMap.containsKey(temp)) {
                        tempMap.put(temp, tempMap.get(temp) + 1);
                    } else {
                        tempMap.put(temp, 1);
                    }
                    while (tempMap.get(temp) > wordMap.get(temp)) {
                        // temp單詞匹配過多，滑窗左邊逐漸縮小艰额，直到彈出多余的單詞
                        String leftStr = s.substring(left, left + wordLen);
                        tempMap.put(leftStr, tempMap.get(leftStr) - 1);
                        left += wordLen;
                    }
                    if (right - left == totalLen) {
                        // 通過滑窗大小來判斷是否匹配成功
                        result.add(left);
                    }
                } else {
                    // 沒有匹配到澄港，滑窗縮小為0，從right部分重新開始
                    tempMap = new HashMap<>();
                    left = right;
                }
            }
        }

        return result;
    }
}