# Python-LeetCode 581 第17招 String (I)
字串是LeetCode常見的題型，從演算法解題的角度來看，字串類似於字元的陣列，所以也可以看成是數列，事實上有許多字串的題目其實跟數列的題目解法是一樣的，它只是出題的一種資料的形式而已。從字串與數列的差異角度來看，字串的成員(字元)通常是一個比較有限的集合，而數列的成員則範圍通常較大。字串的成員稱為alphabet，LeetCode字串題的alphabet通常是限小寫字母，最多也不過就ASCII的範圍。在學術研究上，DNA序列的alphabet只有4個字母，蛋白質序列則是20個字母。alphabet是一個constant size這一點可以看成是字串問題解題上特殊的特性。此外，字串題目中比數列更常會用到字典(hash table)。
本單元中，我們把字串的題目大略區分為以下類別，對於各類別舉出一些題目來說明使用的技巧：
1. 以字串為資料的數列問題。字串只是一種出題的方式，所用的方法，除字串基本操作外，與數列問題並無不同。
2. 字串解析與處理。簡易的語法分析或者要從字串中找出某些結構
3. String matching
4. Palindrome
5. Trie
6. Rolling hash
其中String matching與Palindrome的問題並非僅限於字串，也可以定義在數列上，只是通常放在字串的題目中。而包括Trie 與 Rolling hash則是比較適合small alphabet的資料結構與算法。
註：本單元因為長度較長，所以拆成上下兩個檔案。
## 以字串為資料的數列問題
這一類題目其實就跟數列題一樣，只是輸入與處理時採取字串形式，所以需要一些字串的基本操作。還是可能是難題，因為需要搭配算法，例如排序、Sliding window、DP、Greedy等。因為那些算法已在其他單元中陳述，本單元中僅舉出一些例子。
[(題目連結) 49. Group Anagrams (Medium)](https://leetcode.com/problems/group-anagrams/)
給你些字串，請將屬於相同anagram的字串歸成一組。兩個字串如果使用到的字母相同而排列不同稱為anagram。
這是歸類的問題，同一類我們用一個代表成員來表示的話，我們只要對每一個字串找出他所屬類別的代表成員即可。代表成員可以用它的字母排序後所得的字串來表示，要特別留意Python如何將一個字串內的字母排序。
以下是範例程式。我們先建立一個字典，用defaultdict(list)比較方便，不必特別判斷key值是否存在。接著歷遍每一個字串$s$，計算$s$排序後的字串可以用
''.join(sorted(s))
join是一個很好用的字串函數，語法是
string.join(iterable)
得到的結果是將iterable中每一個成員(必須是字串)，以前面的string當做中介，予以串接後得到一個字串。例如，我們要將字串"qwerty"任兩個字母之間加入一個'-'，就可以用
'-'.join('qwerty')
因為Python的字串是immutable，所以有時候我們會將字串轉換成list，處理完畢後要轉換回字串，就像本例中，我們不能直接排序字串的字母，所以sorted(s)得到的是sorted(list(s))，也就是是一個list，然後用空字串當做中介來串接，就是
''.join(sorted(s))。
在算出排序後的代表成員後我們就將$s$歸入該組。最後我們要的是每一組一個list，這個可以直接取得dict的values()就能直接轉換。
時間複雜度$O(nL\log L)$，$n$是字串個數，$L$是字串長度。
```python=
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
d[''.join(sorted(s))].append(s)
return d.values()
```
[(題目連結) 1061. Lexicographically Smallest Equivalent String (Medium)](https://leetcode.com/problems/lexicographically-smallest-equivalent-string/)
輸入給你兩個相同長度的字串s1與s2，這兩個字串定義了某些字母的等價關係，亦即$s1[i]$與$s2[i]$兩個字母是等價關係，在此等價關係下，請找出另外一個字串baseStr的最小等價字串。最小的意思是lexicographically smallest。
我們要找出所有等價類的最小代表字母，然後將baseStr的字母一一以該字母等價類的代字母替換就可以了。等價類是disjoint set，所以可以用類似union and find的手法來做。事實上，因為字母只有26個，有很多方式都可以達到需求。
我們以unin and find的概念來做此題，同一個等價類以最小的字母當root，將來對每一個字母找到root即可。以下是範例程式。我們先宣告一個字典$p$用來對應parent，寫一個找到root的函數ifind()。一開始，我們對s1與s2的每一對字母，將它們所屬的類別合併成一類，合併時，第10行先找到各自的root r1與r2，然後將大的併給小的，也就是讓字母順序比較小的當root。
計算答案時，只要將baseStr的每一個字母都找到他的root，最後用join串成字串。
時間複雜度方面，因為字母只有26個，所以是linear time。事實上，因為union發生的機會很少(最多26次)，我們對ifind()有做路徑壓縮的狀況下，ifind所花的時間amortize來看就只有一層。
註：對union and find不熟悉的讀者可以參考[Python-LeetCode 581 第13招 Union-and-Find and Minimum spanning tree](/Q-iGBxm0SP69wEztHQnl7A)
```python=
class Solution:
# disjoint set; equivalent class
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
p = defaultdict(str)
def ifind(s):
if not p[s]: return s
p[s] = ifind(p[s])
return p[s]
for c1,c2 in zip(s1,s2):
r1 = ifind(c1); r2 = ifind(c2)
if r1<r2: p[r2] = r1
elif r2<r1: p[r1] = r2
t = "".join([ifind(c) for c in baseStr])
return t
```
[(題目連結) 2391. Minimum Amount of Time to Collect Garbage (Medium)](https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/)
三種回收垃圾分別以M, P, G表示，每一間房子各有若干回收垃圾，第 i 戶以字串garbage[i]表示，例如'GGM'就表示有兩單位的G與一單位的M。有三台資源回收車，每台回收車只收一種垃圾，而且一單位的垃圾需要一單位的時間。一開始三台車都在第0間房子，第 $i$ 間房子移動到第 $i+1$ 間房子需要的時間是$travel[i]$，而且車子必須根據房子編號依序移動，任何時間只有一台車能夠動作。請問總共需要多少時間可以把所有垃圾收集完畢。
仔細考慮這個問題，總需求時間是垃圾的總量加上移動的時間，垃圾的總量很容易計算，剩下的就是車輛的移動時間，由於每台車只能依照房子編號依序移動，所以唯一影響時間的因素就是：每一種垃圾最後出現的房子編號。例如M最後如果出現在編號5，則收M的那台車就必須花費從$0, 1, 2,...,$移動到5的時間。從0移動到 $i$ 的時間也就是$travel[\ ]$的prefix sum。
以下是範例程式。我們先計算移動時間的prefix sum，放在$ptime$。接著用一個字典 $last$ 來記每一種垃圾最後出現的房子編號，歷遍每一戶的垃圾，將數量加入 $total$，將所枚舉PMG三個字元，如果有在此戶中出現，就改寫 $last$ 的值，歷遍後，留下來的就是最後出現的編號，最後輸出答案。
時間複雜度$O(n+m)$，$n$是戶數，$m$是所有garbage字串總長度。
```python=
class Solution:
# find the last i with PGM respectively
def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
ptime = [0]
for t in travel:
ptime.append(ptime[-1]+t)
total = 0
last = {'P':0, 'M':0, 'G':0 }
for i,s in enumerate(garbage):
total += len(s)
for ch in last:
if ch in s: last[ch] = i
#
return total+sum(ptime[i] for i in last.values())
```
接著舉一個字串DP的例子。
[(題目連結) 87. Scramble String (Hard)](https://leetcode.com/problems/scramble-string/)
定義一個字串的以下遞迴操作：
* 如果長度為1，結束；
* 任意選擇一個位置將字串切成左右兩非空字串；
* 選擇交換或不交換左右兩字串；
* 對左右兩字串遞迴進行此操作。
輸入給你兩個長度相同的字串 $s1$ 與 $s2$，請問是否可以將 $s1$ 進行以上操作得到 $s2$。
遞迴定義的東西就遞迴來做，但加上memoization的DP來避免重複檢查。令$dp(l1,r1,l2,r2)$代表$s1[l1:r1]$是否可以變成$s2[l2:r2]$。以下是範例程式。
我們先檢查兩字串內的字母是否相同，這個可以用排序後的字串來檢查(第7行)，其次，如果長度不超過3一定是可以轉變(第8行)。否則，我們就檢查在每一個位置切開的可能(第9行)，對每一個切開的位置考慮交換與不交換兩種可能(第10 ~ 13行)。
時間複雜度$O(n^4\log n)$，$n$是字串長度，表面上dp有四個參數，但每次進入時兩邊長度必然是相等，所以只有$O(n^3)$種狀態，每種狀態花了$O(n\log n)$的時間。第7行如果不用sort來比較，複雜度可以少一個log，但字串長度其實很短，沒有什麼差別。
```python=
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n = len(s1)
@lru_cache(maxsize=None)
def dp(l1,r1,l2,r2):
s,t = s1[l1:r1], s2[l2:r2]
if sorted(s)!=sorted(t): return False
if len(s) <=3: return True
for i in range(1,len(s)):
if dp(l1,l1+i,l2,l2+i) and dp(l1+i,r1,l2+i,r2):
return True
if dp(l1,l1+i,r2-i,r2) and dp(l1+i,r1,l2,r2-i):
return True
return False
#main
ans = dp(0,n,0,n)
return ans
```
接著看一個Sliding window與counter的例子。
[(題目連結) 438. Find All Anagrams in a String (Medium)](https://leetcode.com/problems/find-all-anagrams-in-a-string/)
輸入給你兩個字串 $s$ 與 $p$，請找出 $s$ 所有的substring是 $p$ 的anagram，也就是該子字串是 $p$ 的一個排列(使用字母種類與數量相同)。
很明顯的sliding window的題目，維護好window中屬於p中所需字母的數量，若window大小與 $p$ 的長度一致且滿足所有字母需求，就是一個答案。以下範例程式是使用Counter來當計數器，迴圈不變性為：視窗左端字母在視窗內出現的次數不多於 $p$ 中的數量。每次移動右端一格，調整左端，如果需求數量剛好滿足且視窗長度與 $p$ 的長度一致，就是一個答案。
時間複雜度$O(n+m)$，其中$m,n$分別是兩字串的長度。
```python=
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
pcnt = Counter(p) # goal
scnt = Counter() # current
idx = hit = 0
pos = []
for i,ch in enumerate(s): # move right
scnt[ch] += 1
if scnt[ch] <= pcnt[ch]:
hit += 1
while idx <= i and scnt[s[idx]] > pcnt[s[idx]]:
scnt[s[idx]] -= 1 # move left
idx += 1
if hit == len(p) and idx+len(p)-1 == i:
pos.append(idx) # record ans
# end for
return pos
```
因為本題計數器的大小不超過26，所以固定維護視窗大小與 $p$ 的長度一致，然後直接把計數器拿來比較也是一個方法，但稍微慢一點。
```python=
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
pos = []
m,n = len(s), len(p)
if m < n: return pos
pcnt = Counter(p)
curr = Counter(s[:n-1])
for i in range(n-1,m):
curr[s[i]] += 1
if curr == pcnt: pos.append(i-n+1)
curr[s[i-n+1]] -= 1
return pos
```
接著看一個搜尋的例子。
[(題目連結) 472. Concatenated Words (Hard)](https://leetcode.com/problems/concatenated-words/description/)
輸入給你一些字串 $words$，請找出其中哪些字串可以由其他較短的字串串接而成，較短的字串可以重複使用(請看原題範例)。字串數量不超過$10^4$，每個字串長度不超過30，所有字串長度總合不超過$10^5$。
題目乍看之下好像不知如何下手，字串的個數又很多，但注意到字串的長度很短，這使得枚舉搜尋成為一個可能的解法。
為了避免搜尋到自己，我們將字串根據長度分類，由短到長納入一個集合 $D$ 中，每次檢查一個字串 $s$ 是否可被串接而成時，$D$ 中的字串都是比較短的字串。在檢查字串 $s$ 時，我們嘗試 $s$ 的所有prefix $s[:i]$，如果$s[:i]$在 $D$ 中，我們就搜尋後半段 $s[i:]$ 是否可以被串接而成。
此外，為了避免重複搜尋，我們採取memoization，將搜尋失敗的字串記錄在一個 set 中。
以下是範例程式。初始時，先將所有字串根據長度放入 $W[i]$ 中，$D$ 初始只包含長度為1的字串。第17行開始，由短而長每一回合檢查一種長度的字串，搜尋檢查 $W[i]$ 中的每個字串，完畢後將 $W[i]$ 加入 $D$，第18行的 $fail$ 是紀錄搜尋失敗的字串，要留意變更 $D$ 之後必須重置 $fail$。
搜尋的函數在第8 ~ 15行，先檢查若 $s$ 在 $D$ 中則是True；在 $fail$ 中則是False。若都不是，對 $s$ 的每一個prefix，如果prefix在 $D$ 中且遞迴搜尋後半段也是True的話，則 $s$ 就是可以成功由較短字串串接而成。如果所有前綴都無法成功，則回傳False。
在沒有memoization的情況下，worst case time complexity粗估可能達到$O(n2^L)$，其中$n,L$分別是字串的數量與長度，因為搜尋中的迴圈導致$T(L)=T(L-1)+T(L-2)+\ldots +T(1)$，其中$T(L)$表示長度$L$的字串所需的搜尋時間。
在有memoization的協助下，失敗的搜尋字串不會超過$O(nL)$次，因為每個字串只會有$L$個suffix，更精確一點說，失敗的搜尋字串不會超過$O(M)$，其中$M$是所有字串長度總和，本題保證$M\le 10^5$。每次搜尋需要該字串長度平方的時間，所以總共的時間是$O(ML^2)$。
```python=
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
W = [set() for i in range(31)] # words of length i
for word in words:
W[len(word)].add(word)
ans = []
D = W[1] # containing only str shorter than current
def search(s): # if s is composed of shorter str
if s in D: return True # terminal case
if s in fail: return False # memoization
for i in range(1,len(s)): # try each possible prefix
if s[:i] in D and search(s[i:]):
return True
fail.add(s)
return False
#main
for i in range(2,31): # from short to long
fail = set() # reset memoization
for s in W[i]:
if search(s): ans.append(s)
D |= W[i]
return ans
```
## 字串解析與處理
[(題目連結) 10. Regular Expression Matching (Hard)](https://leetcode.com/problems/regular-expression-matching/)
輸入給你兩個字串 $s$ 與 $p$，其中 $s$ 只包含小寫字母，$p$ 除了小寫字母還可能有'.'與'\*'。其中
* '.' 可以代表任意一個字母。
* '\*' 代表他前方字母可以重複0次或任意多次。
請問在此規則下，$p$ 字串可否表達成 $s$。例如，若$p$="b.a\*w"，則$p$可以表達的字串是b後面接任意一個字母，再接任意數量的a，再接一個w，例如 bqw, 或 bsaw 或 bbaaaaw....等等。本題中$p$ 與 $s$ 的長度皆不超過20。
我們可以用兩個字串的suffix來做DP，令$dp(i,j)$為$s[i:]$與$p[j:]$兩個字串能否相等，以下是top-down memoization的範例程式。以$memo[i,j]$來記錄算過的$dp(i,j)$值，初始條件是$memo[m,n]=True$，此時兩者皆是空字串。遞迴關係式為：
* 若$p[j+1]$ != '\*'，則必須當前的字母配對成功且$d(i+1,j+1)$也是真，$dp(i,j)$才是真；
* 否則，$p[j+1]$ == '\*'，有兩個情形$dp(i,j)$為真：$dp(i,j+2)$為真，也就是星號表示0個；或者當前字母配對且$dp(i+1,j)$為真，也就是星號先給出一個與$s[i]$配對。
其中當前字母配對必須考慮 '.' 的情形，此外，要留意邊界。
時間複雜度為$O(mn)$，其中$m,n$是兩個字串的長度，狀態最多只有$mn$種。
```python=
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m,n = len(s),len(p)
memo = {}
for i in range(m): memo[i,n]=False
memo[m,n] = True
def dp(i,j):
if (i,j) in memo: return memo[i,j]
match = (i<m) and (s[i]==p[j] or p[j]=='.')
if j==n-1 or p[j+1]!='*':
res = match and dp(i+1,j+1)
else: # p=x*
res = dp(i,j+2) or (match and dp(i+1,j))
memo[i,j] = res
return res
#main
return dp(0,0)
```
[(題目連結) 65. Valid Number (Hard)](https://leetcode.com/problems/valid-number/)
很標準的Grammar的parser題目，題目中定義一個合法數字的文法規則，輸入一個字串，判斷它是否是合於文法定義的數字。
這一類的題目只要照著定義寫判斷即可，很多類似題目中會包含遞迴的定義，但本題沒有，只要須依些字串處理的技巧即可。以下是範例程式，題目定義有decimal，我們就寫一個函數判斷是否是decimal；題目有一個定義integer，我們也寫一個函數判斷是否是integer。總之，照著定義寫就好了。
```python=
class Solution:
def isNumber(self, s: str) -> bool:
def decimal(s):
if len(s)==0: return False
if s[0]=='+' or s[0]=='-':
s = s[1:]
if not '.' in s or len(s)==1:
return False
i = 0
while i<len(s) and '0'<=s[i]<='9':
i += 1
if i==len(s) or s[i]!='.':
return False
i += 1
while i<len(s) and '0'<=s[i]<='9':
i += 1
if i<len(s): return False
return True
def integer(s):
if len(s)==0: return False
if s[0]=='+' or s[0]=='-':
s = s[1:]
if len(s)==0: return False
for c in s:
if '0'>c or c>'9': return False
return True
# main
if 'e' in s:
i = s.index('e')
elif 'E' in s:
i = s.index('E')
else:
i = -1
if i>=0:
if not decimal(s[:i]) and not integer(s[:i]):
return False
if not integer(s[i+1:]):
return False
else:
if not decimal(s) and not integer(s):
return False
return True
```
[(題目連結) 224. Basic Calculator (Hard)](https://leetcode.com/problems/basic-calculator/)
輸入一個字串，表示一個由數字與加減法以及括號組成的一個計算式，請計算出其結果，其中，減號可以表示減法或負號。
這題是很標準的資料結構教科書中Expression evaluation的題目，當然計算式經過簡化。題目特別要求不可以用內建函數做，否則Python的eval()就直接搞定了。
這一類的題目是很實際的問題，因為compiler處理程式中的表示式就是要處理這個問題，而且複雜的多。教科書標準做法就是先轉Postfix form，然後利用堆疊做evaluation，以下是範例程式，其中我們把減法與負號用兩個符號來分別表示。如果對於Expression evaluation不熟悉可以查一下書或者網路上的教學，例如 [這一篇](https://www.geeksforgeeks.org/expression-evaluation/) 或 [另一篇](https://cp-algorithms.com/string/expression_parsing.html)。
```python=
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(' ','')
s += ')'
n = len(s)
# to postfix
stk = ['('] # dummy
post = []
i = 0
while i < n:
if s[i] == '(':
stk.append('(')
i = i+1
continue
if '0' <= s[i] <='9':
j = i+1
while j<n and '0'<=s[j]<='9':
j += 1
post.append(int(s[i:j]))
i = j
continue
# otherwise
while stk[-1] != '(':
post.append(stk.pop())
if s[i] == ')':
stk.pop()
elif s[i] == '+':
stk.append('+')
elif s[i] == '-': # neg or minus
if i==0 or s[i-1]=='(':
stk.append('n') # negative
else:
stk.append('-') #minus
#end if
i += 1
#end while
#post += stk[::-1]
# evaluation
stk = []
for token in post:
if token == 'n':
stk[-1] = -stk[-1]
elif token == '+':
p = stk.pop()
stk[-1] += p
elif token == '-':
p = stk.pop()
stk[-1] -= p
else: # operand
stk.append(token)
return stk[-1]
```
## String matching
String matching是一個很重要而基本的問題，是指在一個字串 $s$ 中尋找另外一個字串 $pattern$，通常 $s$ 可能很長，而 $pattern$ 較短。搜尋的要求可能是找到第一個或者是所有出現的位置。這也就是很多文書軟體或搜尋引擎的基本文字搜尋功能。
如果用最基本的方法來找，我們對於每一個可能的起始位置進行比對，假設$n=len(s)$; $m=len(pattern)$。以下是枚舉比對。
```python
for i in range(n-m+1):
if s[i:i+m] == pattern:
print(i)
```
這樣的做法worst case時間複雜度是$O(mn)$，或者更精確的說$O(n(n-m+1))$。事實上，在一般情形下，這個方法表現的並不壞，因為對於大多數的字串來說，兩個字串的比對只要碰到第一個不符的字元就會結束比對，所以
s[i:i+m] == pattern
這行指令花的時間平均來講是很小的。但worst case確實存在，當 $s$ 是個週期重複字串時，就會發生比對很花時間的狀況，極端情形例如
s = "a"\*n
pattern = "a"\*(m-1)+'b'
這個問題那麼重要，當然也發展出了很多有效率的演算法，著名的例如KMP與Boyer-Moore演算法，這些演算法可以達到線性時間。那麼，要不要學呢? 能學當然很好，LeetCode中的題目大多數都有其他解法，看起來是因為LeetCode的目標並非多學特殊演算法，而著重在演算法精神的運用。
很多程式語言中都有提供字串中找字串的函數，而且**很多語言已經內建了線性時間的搜尋函數**，例如Python的string.find()以及C的strstr()。那麼，應該不必學了吧？可是也未必，出題者還是有辦法出類似觀念的題目，再者，學習著名算法也可以學習該算法中的精神。
先看一題簡單的字串搜尋裸題。
[(題目連結) 28. Find the Index of the First Occurrence in a String (Easy)](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
題目很簡單，就是在一個字串中找另外一個字串出現的位置。雖然題目內字串的名字是**在稻草堆裡面找針**，但是本題並不難。
用Python一行指令就可以了，以下是範例程式，此外我們在下面還是列出了用直接手法而不使用string.find()函數來做，其實也是非常簡單的。
時間複雜度方面，利用find()在測資很大的時候是$O(m+n)$，而自己寫是$O(mn)$，由於測資很小，並非複雜度好的跑得快。
```python=
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)
# trival method
n=len(haystack); m=len(needle)
for i in range(n-m+1):
if haystack[i:i+m]==needle:
return i
return -1
```
接著我們來看一題需要string matching的應用題。
[(題目連結) 1764. Form Array by Concatenating Subarrays of Another Array (Medium)](https://leetcode.com/problems/form-array-by-concatenating-subarrays-of-another-array/)
輸入給你 $n$ 個數列組成的陣列$groups$，另外再給一個數列$nums$，請問你可否在$nums$中找出$n$個disjoint的subarray，他們依序就是$groups$中的$n$個數列。
在大方向上，我們先找$groups[0]$在$nums$中出現的位置，如果有多個位置，顯然應該要greedy，找第一個出現的只會好不會壞，然後依序往下(不可重疊)找出$groups$中的所有數列，如果成功，答案就是True，否則，過程中失敗，答案就是False。
剩下問題是如何在一個數列中找另外一個數列了。
數列中找數列與字串中找字串基本上是一樣的，可以用類似前一題的trivial algorithm。但這裡我們介紹一個有趣的方法來利用字串的find()，那就是我們把數列轉換成字串。請看以下範例程式。
一開始就先把$nums$轉成字串，用str將數字轉換為字串後，再以join將它們合併，彼此之間加上一個句點，以便分隔，否則無法區分$[12,34]$與$[123,4]$。接著歷遍$groups$，每一個數列也都依相同方法轉換為字串，留意到我們頭尾加上一個空字串，這是為了防止數列只有一個元素時，如果沒有間隔符號可能會找到一個大數字中的一部分。另外一個要注意的是find()第一個參數是要找的對象，第二個參數是開始尋找的位置(省略的話預設為0)。所以我們可以從前一個之後的地方開始找，程式第4, 7與9行就是控制搜尋起始位置。第9行的減1是不要跳掉最後一個句點。
時間複雜度是linear time，但轉換字串需要花一些時間(也是linear time)。
```python=
class Solution:
def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
s = '.'.join(['']+[str(i) for i in nums]+[''])
p = 0
for g in groups:
gs = '.'.join(['']+[str(i) for i in g]+[''])
i = s.find(gs,p)
if i==-1: return False
p = i+len(gs)-1 # not excluding last period
return True
```
下一題也是利用string.find()來完成的題目。
[(題目連結) 1910. Remove All Occurrences of a Substring (Medium)](https://leetcode.com/problems/remove-all-occurrences-of-a-substring/)
題目很簡單，給兩個字串$s$與$part$，持續找出$s$中第一個出現$part$的地方，將它移除，直到沒有$part$出現為止。
是個模擬題，解法也很簡單，只要會用find與刪除字串中一部分的方法就行了。以下是範例程式。留意字串是immutable，刪除時另外構建就可以了。
```python=
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
k = len(part)
while True:
i = s.find(part)
if i<0: return s
s = s[:i]+s[i+k:]
#
```
下面這一題很有意思。
[(題目連結) 1392. Longest Happy Prefix (Hard)](https://leetcode.com/problems/longest-happy-prefix/)
題目是說給你一個字串$s$，要找出(除了$s$自己之外)最長的一段前綴(prefix)，該前綴也是$s$的後綴(suffix)，也就是說，若$s$的長度為$n$，要找出最大的$k<n$，滿足$s[:k]==s[-k:]$。
直接的方法是由大到小或由小到大嘗試$k$值，例如
```python=
for k in range(n-1,-1,-1):
if s[:k]==s[-k:]: return s[:k]
```
但可能花費$O(n^2)$的時間。
為什麼會說這個題目很有趣呢？因為它要算的就是KMP演算法中的精神所在。不熟悉的讀者可以先看看KMP的教學文件，網路上可以找到很多，例如 [CP-Algorithm-KMP](https://cp-algorithms.com/string/prefix-function.html)這一篇寫得就很清楚容易了解。簡單來說，KMP在字串$s$中搜尋字串$p$時，會先計算$p$的一個**prefix function** (多數文獻中稱為failure function)，對於每一個位置$i$，這個prefix function就是最大的$k$，滿足長度為$k$的前綴等於以$i$結尾的後綴($p[:k]==p[i-k+1:i+1]$)。而KMP的算法精神在於
1. prefix function可以很有效率的被計算出來，是一種DP的方法。
2. 在$s$中搜尋$p$時，利用$p$的prefix function，當比對失敗時，可以直接跳到下一個比對位置而非重頭開始比對，減少重複比對。
以下是範例程式，其中的$pi$就是prefix function，詳細內容請參考上述文件。時間複雜度是線性。
如同前面提到的，不使用KMP也可以做這題，方法是用Rolling hash，後面章節中會在說明方法。
```python=
class Solution:
# it is indeed the KMP failure function, aka prefix
# pi[i]=j is longest prefix = suffix, s[:j] = s[i-j+1:i+1]
def longestPrefix(self, s: str) -> str:
n = len(s)
pi = [0]*n
j = 0
for i in range(1,n):
if s[i] == s[j]:
j += 1
pi[i] = j
continue
# otherwise
while j>0 and s[j]!=s[i]:
j = pi[j-1]
j += (s[j]==s[i])
pi[i] = j
#
return s[:pi[-1]]
```
**End of String (上)**
Sign in with Wallet
Connect another wallet