30 Substring with Concatenation of All Words

两种解法，第一种解法采用模拟的方法，将字符串做分割后，判断得到的字符串是否满足要求。

第二种解法: 使用sliding window，控制start, end指针，截断相关的字符串， 如果满足条件，那么扩展end，如果出现不对的情况，在进行start指针调整，使用哈希表记录指针需要移动的位置，方便进行后面的操作。

注意问题：words里面存在重复的单词，满足条件的字符串的位置不一定是整数个word之后起始的位置。

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if words == []:
            return []
        ans = []
        word_count = len(words)
        word_length = len(words[0])
        length = word_count * word_length
        i = 0
        temp = {}
        for word in words:
            if word not in temp:
                temp[word] = 1
            else:
                temp[word] += 1
        while i <= len(s) - length:
            start_position, end_position = i, i + length
            current_str = s[start_position: end_position]
            j = 0
            d = {}
            flag = True
            while j < length:
                cur_word = current_str[j:j+word_length]
                j+= word_length
                if cur_word not in words:
                    flag = False
                    break
                else:
                    if cur_word not in d:
                        d[cur_word] = 1
                    else:
                        d[cur_word] += 1
            if flag and d == temp:
                ans.append(i)
            i += 1
        return ansCopy
class Solution(object)
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if s == "" or len(words) == 0:
            return []
        wordDict = {}
        for word in words:
            if word in wordDict:
                wordDict[word] += 1
            else:
                wordDict[word] = 1
        wordLen, wordNum = len(words[0]), len(words)
        sLen = len(s)
        if sLen < wordLen * wordNum:
            return []
        result = []
        for i in range(wordLen):  ## important!!
            left = i
            tmpDict = {}
            count = 0
            j = i
            while j < sLen-wordLen+1:
                tmp = s[j:j+wordLen]
                j += wordLen
                if tmp in wordDict:
                    if tmp in tmpDict:
                        tmpDict[tmp] += 1
                    else:
                        tmpDict[tmp] = 1
                    if tmpDict[tmp] <= wordDict[tmp]:
                        count += 1
                    else:
                        while tmpDict[tmp] > wordDict[tmp]:
                            t = s[left:left+wordLen]
                            left += wordLen
                            tmpDict[t] -= 1
                            if tmpDict[t] < wordDict[t]:
                                count -= 1
                    if count == wordNum:
                        result.append(left)
                        t = s[left:left + wordLen]
                        tmpDict[t] -= 1
                        left += wordLen
                        count -= 1
                else:
                    tmpDict = {}
                    count = 0
                    left = j
        return result