CodeFights.py/findSubstrings.py at master · Adam-Hoelscher/CodeFights.py · GitHub

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
def findSubstrings(words, parts):

    strings_of_length = dict()

    def add_to_tree(t, val):
        if len(val) == 1:
            t[val[0]] = False
        else:
            if val[0] not in t: t[val[0]] = dict()
            next_t = t[val[0]]
            add_to_tree(next_t, val[1:])

    for p in parts:
        l = len(p)
        if l not in strings_of_length: strings_of_length[l] = dict()
        add_to_tree(strings_of_length[l], p)

    def check(string, tree, top = True):

        if not string: return(False)
        if string[0] not in tree: return(False)

        if top:
            temp = '['
        else:
            temp = ''

        next_tree = tree[string[0]]
        if next_tree:
            next_check = check(string[1:], next_tree, False)
            if not next_check: return(False)
            temp += (string[0] + next_check)
        else:
            temp += (string[0] + ']' + string[1:])

        return(temp)

    for l in sorted(strings_of_length.keys(), reverse=True):
        for word_pos, word in enumerate(words):
            if '[' not in word:
                for letter_pos, letter in enumerate(word):
                    new_end = check(word[letter_pos:], strings_of_length[l])
                    if new_end:
                        words[word_pos] = word[:letter_pos] + new_end
                        break

    return(words)