Fork me on GitHub

Substring with Concatenation of All Words

Posted on

Description

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

TLE Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        dic = {}
        alphabet = {}
        for word in words:
            if dic.get(word) is None:
                dic[word] = 1
            else:
                dic[word] += 1
            if alphabet.get(word[0]) is None:
                alphabet[word[0]] = [word]
            else:
                alphabet[word[0]].append(word)

        ret = []
        i = 0
        while i < len(s):
            while i < len(s) and alphabet.get(s[i]) is None:
                i += 1
            if i == len(s):
                return ret
            if self.valid(i, s, dic, alphabet, ret) == True:
                ret.append(i)
            i += 1
        
        return ret
                    
    def valid(self, i, s, word_dict, alphabet, ret):
        if word_dict == {}:
            return True
        if i >= len(s):
            return False
        
        flag = False
        item_list = alphabet.get(s[i])
        if item_list is None:
            return False
        
        
        for item in item_list:
            if i + len(item) <= len(s) and item == s[i : i + len(item)] and word_dict.get(item):
                self.clear(word_dict, item, -1)
                if self.valid(i + len(item), s, word_dict, alphabet, ret) == True:
                    flag = True
                self.clear(word_dict, item, 1)
        
        return flag
            
    def clear(self, dic, item, incre):
        t = dic.get(item)
        if t is None:
            dic[item] = 1
            return
        if t == 1 and incre < 0:
            del dic[item]
            return
        
        dic[item] += incre
        return

Solution