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
|
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)
setrecursionlimit(int(2e9))
class Arr:
array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
graph = staticmethod(lambda size=N: [[] for _ in range(size)])
class Math:
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
class Std:
class TrieNode:
"""TrieNode class can quickly process string prefixes, a common feature used in applications like autocomplete and spell checking."""
_sid_cnt = 0
def __init__(self):
"""Initialize children dictionary and cost. The trie tree is a 26-ary tree."""
self.children_ = {}
self._sid = -1
def add(self, word: str) -> int:
"""Add a word to the trie with the associated cost and return a unique ID."""
node = self
for c in word:
if c not in node.children_:
node.children_[c] = Std.TrieNode()
node = node.children_[c]
return node._sid
class Solution:
def minValidStrings(self, words: List[str], target: str) -> int:
n = len(target)
trie = Std.TrieNode()
for word in words:
trie.add(word)
@lru_cache(None)
def dfs(i: int) -> int:
nonlocal trie
if i == n:
return 0
res = INF
node = trie
for j in range(i, n):
c = target[j]
if c not in node.children_:
break
sub_res = dfs(j + 1)
res = Math.min(res, sub_res + 1)
node = node.children_[c]
return res
result = dfs(0)
dfs.cache_clear()
return result if result != INF else -1
|