Count Words Obtained After Adding a Letter LeetCode solution in Python

1
# Brute Force
2
# O(S * T); S := len(startWors); T := len(targetWords)
3
# TLE
4
class Solution:
5
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
6
        cnt = 0
7
        for target in targetWords:
8
            for start in startWords:
9
                if (
10
                    len(target) - len(start) == 1
11
                    and len(set(list(target)) - set(list(start))) == 1
12
                ):
13
                    cnt += 1
14
                    break
15
        return cnt
16

17

18
# Sort + HashSet Lookup
19
# O(S + T) Time
20
class Solution:
21
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
22
        # Sort each start word and add it to a hash set
23
        startWords_sorted = set()
24
        # O(S*26*log(26))
25
        for word in startWords:
26
            startWords_sorted.add("".join(sorted(list(word))))
27

28
        # sort each target word and add it to a list
29
        # O(T*26*log(26))
30
        targetWords_sorted = []
31
        for word in targetWords:
32
            targetWords_sorted.append(sorted(list(word)))
33

34
        # for each sorted target word, we remove a single character and
35
        # check if the resulting word is in the startWords_sorted
36
        # if it is, we increment cnt and break the inner loop
37
        # otherwise we keep removing until we either find a hit or reach the
38
        # end of the string
39
        # O(T*26) = O(T)
40
        cnt = 0
41
        for target in targetWords_sorted:
42
            for i in range(len(target)):
43
                w = target[:i] + target[i + 1 :]
44
                w = "".join(w)
45
                if w in startWords_sorted:
46
                    cnt += 1
47
                    break
48

49
        return cnt
50

51

52
# Using Bit Mask
53
# O(S + T) Time
54
# Similar algorithm as the one above, implemented using a bit mask to avoid the sorts
55
class Solution:
56
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
57
        start_set = set()
58
        # O(S * 26)
59
        for word in startWords:
60
            m = 0
61
            for ch in word:
62
                i = ord(ch) - ord("a")
63
                m |= 1 << i
64
            start_set.add(m)
65

66
        # O(T * 2 * 26)
67
        cnt = 0
68
        for word in targetWords:
69
            m = 0
70
            for ch in word:
71
                i = ord(ch) - ord("a")
72
                m |= 1 << i
73

74
            for ch in word:
75
                i = ord(ch) - ord("a")
76
                if m ^ (1 << i) in start_set:
77
                    cnt += 1
78
                    break
79
        return cnt