-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathbreaking_bad.py
More file actions
124 lines (99 loc) · 3.73 KB
/
breaking_bad.py
File metadata and controls
124 lines (99 loc) · 3.73 KB
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
"""
Breaking Bad Symbol Matching
Given an array of words and an array of symbols, display each word with its
matched symbol surrounded by square brackets. If a word matches more than one
symbol, choose the one with the longest length.
Reference: https://en.wikipedia.org/wiki/Trie
Complexity:
Time: O(n * m) for brute force, O(n * k) for trie-based approach
Space: O(n * m) for storing results
"""
from __future__ import annotations
import re
from functools import reduce
def match_symbol(words: list[str], symbols: list[str]) -> list[str]:
"""Match symbols in words using regex and surround matches with brackets.
Args:
words: List of words to search through.
symbols: List of symbols to match within the words.
Returns:
List of words with matched symbols surrounded by square brackets.
Examples:
>>> match_symbol(['Google'], ['le'])
['Goog[le]']
"""
combined = []
for symbol in symbols:
for word in words:
match = re.search(symbol, word)
if match:
combined.append(re.sub(symbol, f"[{symbol}]", word))
return combined
def match_symbol_1(words: list[str], symbols: list[str]) -> list[str]:
"""Match the longest symbol in each word using sorted symbol list.
Args:
words: List of words to search through.
symbols: List of symbols to match, sorted by length descending.
Returns:
List of words with the longest matched symbol bracketed.
Examples:
>>> match_symbol_1(['Microsoft'], ['i', 'cro'])
['Mi[cro]soft']
"""
result = []
symbols = sorted(symbols, key=lambda item: len(item), reverse=True)
for word in words:
word_replaced = ""
for symbol in symbols:
if word.find(symbol) != -1:
word_replaced = word.replace(symbol, "[" + symbol + "]")
result.append(word_replaced)
break
if word_replaced == "":
result.append(word)
return result
class _TrieNode:
"""Internal trie node for the bracket function."""
def __init__(self) -> None:
self.children: dict[str, _TrieNode] = {}
self.symbol: str | None = None
def bracket(words: list[str], symbols: list[str]) -> tuple[str, ...]:
"""Match the longest symbol in each word using a trie-based approach.
Args:
words: List of words to search through.
symbols: List of symbols to build the trie from.
Returns:
Tuple of words with the longest matched symbol bracketed.
Examples:
>>> bracket(['Amazon', 'Microsoft', 'Google'], ['Am', 'cro', 'le'])
('[Am]azon', 'Mi[cro]soft', 'Goog[le]')
"""
root = _TrieNode()
for symbol in symbols:
node = root
for char in symbol:
if char not in node.children:
node.children[char] = _TrieNode()
node = node.children[char]
node.symbol = symbol
matched = {}
for word in words:
index = 0
symbol_list = []
while index < len(word):
cursor, node = index, root
while cursor < len(word) and word[cursor] in node.children:
node = node.children[word[cursor]]
if node.symbol is not None:
symbol_list.append(
(cursor + 1 - len(node.symbol), cursor + 1, node.symbol)
)
cursor += 1
index += 1
if len(symbol_list) > 0:
best = reduce(
lambda x, y: x if x[1] - x[0] >= y[1] - y[0] else y,
symbol_list,
)
matched[word] = f"{word[: best[0]]}[{best[2]}]{word[best[1] :]}"
return tuple(matched.get(word, word) for word in words)