串聯(lián)所有單詞的子串

給定一個(gè)字符串 s 和一些長(zhǎng)度相同的單詞 words缨睡。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置搔弄。

注意子串要與 words 中的單詞完全匹配，中間不能有其他字符文兑，但不需要考慮 words 中單詞串聯(lián)的順序盒刚。

 

示例 1：

輸入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" 。
輸出的順序不重要, [9,0] 也是有效答案绿贞。
示例 2：

輸入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
輸出：[]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有伪冰。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處樟蠕。

解答

# -*- coding:utf-8 -*-

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not s or not words:
            return []
        from collections import Counter
        word_num = len(words)
        word_len = len(words[0])  # 題目中單詞長(zhǎng)度都相同
        window_len = word_num * word_len  # 滑動(dòng)窗口的長(zhǎng)度
        window_left = 0  # 滑動(dòng)窗口的左邊索引
        result_start_index_list = []  # 輸出結(jié)果：所有符合條件的滑動(dòng)窗口的左邊索引
        target_counter = Counter(words)  # 因?yàn)榭梢詠y序，因此通過統(tǒng)計(jì)單詞出現(xiàn)次數(shù)是否相同來比較靠柑。
        while window_left + window_len <= len(s):
            cur_word_list = []
            i = window_left
            # 將窗口內(nèi)按照單詞長(zhǎng)度切割字符串寨辩，添加到cur_word_list中
            flag = True
            for j in range(word_num):
                cur_word = s[i:i+word_len]
                # 優(yōu)化: 當(dāng)某個(gè)單詞不在words無(wú)需再判斷后面
                if cur_word not in words: 
                    flag = False
                    break
                    
                cur_word_list.append(cur_word)
                i += word_len
                
            # 比較結(jié)果
            if flag and Counter(cur_word_list) == target_counter:
                result_start_index_list.append(window_left)

            # 滑動(dòng)窗口往左移動(dòng)一位
            window_left += 1

        return result_start_index_list

if __name__ == '__main__':
    s = "barfoothefoobarman"
    words = ["foo", "bar"]

    obj = Solution()
    result = obj.findSubstring(s, words)
    print('result:', result)

1. 思路

• 該題可以使用滑動(dòng)窗口求解。窗口長(zhǎng)度為words的總長(zhǎng)度歼冰，窗口從左到右移動(dòng)一位靡狞，按照單詞長(zhǎng)度將窗口分割成單詞，從而比較結(jié)果隔嫡。

2. 步驟

• 從左向右每個(gè)字符每個(gè)字符遍歷字符串s甸怕，按照單詞長(zhǎng)度切割，最后和哈希（words）進(jìn)行比較
• 每遍歷一次腮恩，記錄相應(yīng)復(fù)合條件的位置
• 輸出位置集合

3. 注意點(diǎn)

• 因?yàn)榭梢詠y序拼接梢杭，因此這里使用collections的Counter來統(tǒng)計(jì)單詞出現(xiàn)的次數(shù), 來判斷是否滿足條件。
• 優(yōu)化: 當(dāng)某個(gè)單詞不在words中則無(wú)需再判斷