https://leetcode.com/discuss/interview-question/281470/
class TrieNode:
def __init__(self):
self.map = dict()
self.end = False
def add_word(root, word):
for w in word:
if w not in root.map:
root.map[w] = TrieNode()
root = root.map[w]
root.end = True
def at_most_one_typo(word, trie_root, typo=True):
for i, w in enumerate(word):
if w in trie_root.map:
trie_root = trie_root.map[w]
elif typo:
for next_node in trie_root.map.values():
if at_most_one_typo(word[i+1:], next_node, typo=False):
return True
return False
else:
return False
return trie_root.end
def solve(words, word_dict):
root = TrieNode()
for word in word_dict:
add_word(root, word)
for word in words:
print(word, at_most_one_typo(word, root))
if __name__ == '__main__':
word_dict = ['apple', 'banana', 'orange']
words = ['banana', 'banena', 'banxnn','apple','applx','steve','xpple']
solve(words, word_dict)https://leetcode.com/discuss/interview-question/643158/google-phone-faulty-keyboard
from functools import lru_cache
# Trie class
class TrieNode:
def __init__(self):
self.map = dict()
self.end = False
def add_word(node, word):
for w in word:
if w in node.map:
node = node.map[w]
else:
tmp = TrieNode()
node.map[w], node = tmp, tmp
node.end = True
def solve(s, dictionary):
root = TrieNode()
for word in dictionary:
add_word(root, word)
@lru_cache(None)
def helper(ind):
res = []
curr = ''
tmp = root
i = ind
while(i < len(s)):
c = s[i]
if(c == ' '):
if(not curr or tmp.end):
# If curr is empty or the last word was in dictionary
comb1 = helper(i+1)
for comb in comb1:
if(curr):
res.append(curr + ' ' + comb)
else:
res.append(comb)
c = 'e'
if c in tmp.map:
curr += c
tmp = tmp.map[c]
else:
break
i += 1
if i==len(s) and tmp.end:
res.append(curr)
return res
return helper(0)
if __name__ == '__main__':
dictionary = {"like", " ", "explore", "toe", "universe", "rse", "I", "to", "lik"}
print(solve("I lik to xplor univ rs ", dictionary))
print(solve("lik to xplor univ rs ", dictionary))
print(solve("to xplor univ rs ", dictionary))
print(solve("xplor univ rs ", dictionary))
print(solve("univ rs ", dictionary))
dictionary.add("expoloreeuniverse")
print(solve(" xplor univ rs ", dictionary))#!/usr/bin/env python
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
from __builtin__ import xrange as range
from future_builtins import ascii, filter, hex, map, oct, zip
############################################################################
# ACTUAL CODE
############################################################################
class Fenwick:
def __init__(self, data):
n = len(data)
self.orig = [0] * n
self.tree = [0] * (n+1)
self.maxn = n + 1
for i, d in enumerate(data):
self.update(i, d)
def update(self, i, val):
self.orig[i], val = val, val - self.orig[i]
k = i + 1
while(k < self.maxn):
self.tree[k] += val
k += k & -k
def cumm(self, i):
k = i + 1
res = 0
while(k > 0):
res += self.tree[k]
k -= k & -k
return res
def query(self, i, j):
return self.cumm(j) - self.cumm(i-1)
def main():
def solve():
n, q = map(int, input().strip().split())
data = list(map(int, input().strip().split()))
fen = Fenwick([(-val if i%2 == 1 else val) for i, val in enumerate(data)])
fenA = Fenwick([(i+1) * (-val if i%2==1 else val) for i,val in enumerate(data)])
res = 0
for i in range(q):
t, a, b = input().split()
if(t == 'U'):
ii = int(a) - 1
val = int(b)
fen.update(ii, (-val if ii%2==1 else val))
fenA.update(ii, (ii+1)*(-val if ii%2==1 else val))
else:
ii, jj = int(a)-1, int(b)-1
curr = fenA.query(int(a)-1, int(b)-1)
curr -= (int(a)-1)*fen.query(int(a)-1, int(b)-1)
if(fen.orig[int(a)-1] < 0):
curr = -curr
res += curr
return res
tc = int(input().strip())
for i in range(1, tc+1):
# Kickstart
ans = solve()
print('Case #' + str(i) + ': ' + str(ans))
############################################################################
# FAST-IO
# PyRIVAL
############################################################################
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
"""Prints the values to a stream, or to sys.stdout by default."""
sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
at_start = True
for x in args:
if not at_start:
file.write(sep)
file.write(str(x))
at_start = False
file.write(kwargs.pop("end", "\n"))
if kwargs.pop("flush", False):
file.flush()
if sys.version_info[0] < 3:
sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
############################################################################
## DRIVER # PROGRAM ########################################################
if __name__ == "__main__":
main()