-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathB_String_Fusion.py
79 lines (59 loc) · 1.36 KB
/
B_String_Fusion.py
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# class TreeNode:
# def __init__(self):
# self.is_end = False
# self.children = [None for i in range(26)]
# class Trie:
# def __init__(self):
# self.root = TreeNode()
# def insert(self, word: str) -> None:
# curr = self.root
# for c in word:
# idx = ord(c) - ord('a')
# if not curr.children[idx]:
# curr.children[idx] = TreeNode()
# curr = curr.children[idx]
# curr.is_end = True
# print(self.count)
# n = int(input())
# dictionary = Trie()
# for t in range(n):
# word = input()
# dictionary.insert(word)
def collapse(a, b):
n, m = len(a), len(b)
if len(a) == 0:
return m
if len(b) == 0:
return n
i, j = len(a) - 1, 0
while a[i] == b[j]:
i -= 1
j += 1
n -= 1
m -= 1
if j > len(b) - 1 or i < 0:
break
return m + n
def collarpse2(b, a):
n, m = len(b), len(a)
if len(b) == 0:
return m
if len(a) == 0:
return n
i, j = len(b) - 1, 0
while b[i] == a[j]:
i -= 1
j += 1
n -= 1
m -= 1
if j > len(a) - 1 or i < 0:
break
return m + n
n = int(input())
words = []
for i in range(n):
word = input()
words.append(word)
memo = {}
count = 0
print(count)