030. Substring with Concatenation of All Words

题目链接：30. Substring with Concatenation of All Words

题目

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.

Example 1:

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 组成子串起始位置，words内可能会有重复元素。

找到的子串内不可以包含其他非words内的元素，也不可以多次使用words内元素。

双循环算法

• 用字典来统计words中每个单词出现的次数。

• 因为words中的单词都是相同大小的，所以可以直接从s中截取固定大小的子串判读是否在words中出现。

• 每轮检测中，使用cur_dict判断减少次数，如果降为负数，则表示重复出现。

class Solution(object):
    def findSubstring(self, s, words):
        if len(words) == 0:
            return []
        wordsMap = {}
        for word in words:
            if word not in wordsMap:
                wordsMap[word] = 1
            else:
                wordsMap[word] += 1
        len_words = len(words[0])
        num_words = len(words)
        ans = []
        
        for i in range(len(s) - len_words * num_words + 1):
            j = 0
            cur_dict = wordsMap.copy()
            while j < num_words:
                word = s[i + len_words * j:i + len_words * j + len_words]
                if word not in wordsMap:
                    break
                if word in cur_dict:
                    cur_dict[word] -= 1
                if cur_dict[word] < 0:
                    break
                j += 1
            if j == num_words:
                ans.append(i)
        return ans

if __name__ == '__main__':
    solu = Solution()
    s, words = 'barfoothefoobarman', ['foo', 'bar']
    print(solu.findSubstring(s, words))

最长子串算法

class Solution:
    def findSubstring(self, s, words):
        if not s or words==[]:
            return []
        lenstr=len(s)
        lenword=len(words[0])
        lensubstr=len(words)*lenword
        times={}
        for word in words:
            if word in times:
                times[word]+=1
            else:
                times[word]=1
        ans=[]
        for i in range(min(lenword,lenstr-lensubstr+1)):
            # lenstr挨个来，所以只需lenword次即可
            self.findAnswer(i,lenstr,lenword,lensubstr,s,times,ans)
        return ans
    
    def findAnswer(self,strstart,lenstr,lenword,lensubstr,s,times,ans):
        wordstart=strstart
        curr={}
        while strstart+lensubstr<=lenstr:
            word=s[wordstart:wordstart+lenword]
            wordstart+=lenword
            if word not in times:
                strstart=wordstart
                curr.clear()
            else:
                if word in curr:
                    curr[word]+=1
                else:
                    curr[word]=1
                # 如果大于已有的，尝试删除一些内容。
                while curr[word]>times[word]:
                    curr[s[strstart:strstart+lenword]]-=1
                    strstart+=lenword
                if wordstart-strstart==lensubstr:
                    ans.append(strstart)

if __name__ == "__main__":
    test = Solution()
    s, words = 'barfoothefoobarman', ['foo', 'bar']
    print(test.findSubstring(s, words))