1. 字符串算法專題深度解析字符串處理是算法領(lǐng)域的核心基礎(chǔ)也是各大技術(shù)面試中的高頻考點(diǎn)。今天咱們來(lái)聊聊字符串專題中的幾個(gè)硬核知識(shí)點(diǎn)這些都是我在算法訓(xùn)練和實(shí)際工程中總結(jié)的實(shí)戰(zhàn)經(jīng)驗(yàn)。字符串算法看似簡(jiǎn)單但想要寫出高效、優(yōu)雅的解決方案需要掌握一些關(guān)鍵技巧和思維模式。特別是當(dāng)處理大規(guī)模文本數(shù)據(jù)時(shí)算法效率的差異會(huì)導(dǎo)致性能上的天壤之別。下面我就結(jié)合幾個(gè)典型問(wèn)題帶大家深入理解字符串處理的精髓。提示建議在閱讀本文時(shí)準(zhǔn)備好紙筆跟著示例手動(dòng)模擬算法執(zhí)行過(guò)程這種手推方法能幫你真正理解算法本質(zhì)。1.1 字符串匹配的三種境界字符串匹配問(wèn)題可以說(shuō)是算法界的Hello World但不同解法之間的效率差異可能達(dá)到百萬(wàn)倍。我們來(lái)看三種典型的解決方案暴力匹配法- 時(shí)間復(fù)雜度O(mn)def brute_force(text, pattern): n, m len(text), len(pattern) for i in range(n - m 1): j 0 while j m and text[ij] pattern[j]: j 1 if j m: return i return -1KMP算法- 時(shí)間復(fù)雜度O(mn)def kmp(text, pattern): # 構(gòu)建部分匹配表 lps [0] * len(pattern) length 0 i 1 while i len(pattern): if pattern[i] pattern[length]: length 1 lps[i] length i 1 else: if length ! 0: length lps[length-1] else: lps[i] 0 i 1 # 開始匹配 i j 0 while i len(text): if text[i] pattern[j]: i 1 j 1 if j len(pattern): return i - j else: if j ! 0: j lps[j-1] else: i 1 return -1Boyer-Moore算法- 實(shí)踐中最快的單模式匹配算法Boyer-Moore算法采用了從右向左比較的策略并利用壞字符規(guī)則和好后綴規(guī)則實(shí)現(xiàn)跳躍式匹配在真實(shí)場(chǎng)景中往往能達(dá)到亞線性時(shí)間復(fù)雜度。避坑指南KMP算法雖然理論復(fù)雜度優(yōu)秀但在實(shí)際應(yīng)用中由于預(yù)處理開銷和緩存不友好等問(wèn)題對(duì)于短模式串(長(zhǎng)度10)可能還不如暴力法快。要根據(jù)具體場(chǎng)景選擇合適的算法。1.2 回文串處理的奇偶陷阱回文串問(wèn)題是字符串專題中的另一個(gè)經(jīng)典類別?？此坪?jiǎn)單的問(wèn)題背后隱藏著不少陷阱# 中心擴(kuò)展法 - 處理奇偶回文的統(tǒng)一方法 def longestPalindrome(s): def expand(l, r): while l 0 and r len(s) and s[l] s[r]: l - 1 r 1 return s[l1:r] res for i in range(len(s)): # 奇數(shù)長(zhǎng)度 tmp expand(i, i) if len(tmp) len(res): res tmp # 偶數(shù)長(zhǎng)度 tmp expand(i, i1) if len(tmp) len(res): res tmp return res這個(gè)解法巧妙之處在于通過(guò)中心擴(kuò)展統(tǒng)一處理了奇偶兩種情況。在實(shí)際編碼面試中很多候選人會(huì)忽略偶數(shù)長(zhǎng)度回文的情況導(dǎo)致解決方案不完整。1.3 字符串翻轉(zhuǎn)的六種姿勢(shì)字符串翻轉(zhuǎn)看似簡(jiǎn)單但不同的實(shí)現(xiàn)方式反映了不同的編程思維使用切片Pythonic方式s hello print(s[::-1]) # olleh使用reversed函數(shù)s hello print(.join(reversed(s))) # olleh雙指針?lè)ㄟm用于不能使用庫(kù)函數(shù)的場(chǎng)景def reverse_string(s): left, right 0, len(s) - 1 while left right: s[left], s[right] s[right], s[left] left 1 right - 1 return s遞歸法不推薦實(shí)際使用教學(xué)目的def reverse_string(s): if len(s) 1: return s return reverse_string(s[1:]) s[0]使用棧理解數(shù)據(jù)結(jié)構(gòu)的好例子def reverse_string(s): stack list(s) res [] while stack: res.append(stack.pop()) return .join(res)使用reduce函數(shù)函數(shù)式編程風(fēng)格from functools import reduce s hello print(reduce(lambda x, y: y x, s)) # olleh性能實(shí)測(cè)在Python中切片法[::-1]是最快的比雙指針?lè)?-5倍。但在C等語(yǔ)言中雙指針原地交換才是最優(yōu)解。2. 字符串編碼與轉(zhuǎn)換技巧2.1 Unicode與編碼陷阱處理多語(yǔ)言文本時(shí)編碼問(wèn)題是個(gè)大坑。來(lái)看幾個(gè)常見問(wèn)題及解決方案計(jì)算實(shí)際字符數(shù)不是字節(jié)數(shù)s 你好hello print(len(s)) # 7 (字節(jié)數(shù)) print(len(s.encode(utf-8))) # 11 (字節(jié)數(shù)) print(len([c for c in s])) # 7 (錯(cuò)誤方法) print(len(s.encode(utf-16-le))//2) # 7 (錯(cuò)誤方法) # 正確方法 import unicodedata print(unicodedata.normalize(NFC, s)) # 標(biāo)準(zhǔn)化 print(len(unicodedata.normalize(NFC, s))) # 5處理特殊字符# 過(guò)濾控制字符 def remove_control_chars(s): return .join(ch for ch in s if unicodedata.category(ch)[0] ! C) # 處理組合字符 s café # e\u0301形式 print(len(s)) # 5 normalized unicodedata.normalize(NFC, s) print(len(normalized)) # 42.2 字符串與數(shù)字的轉(zhuǎn)換優(yōu)化這類問(wèn)題在算法競(jìng)賽和面試中經(jīng)常出現(xiàn)字符串轉(zhuǎn)整數(shù)atoidef atoi(s): s s.strip() if not s: return 0 sign -1 if s[0] - else 1 if s[0] in -: s s[1:] res 0 for ch in s: if not ch.isdigit(): break res res * 10 (ord(ch) - ord(0)) return max(-2**31, min(sign * res, 2**31-1))整數(shù)轉(zhuǎn)字符串itoadef itoa(n): if n 0: return 0 sign - if n 0 else n abs(n) res [] while n 0: res.append(chr(ord(0) n % 10)) n n // 10 return sign .join(reversed(res))性能技巧在Python中str()和int()內(nèi)置函數(shù)已經(jīng)高度優(yōu)化通常比自己實(shí)現(xiàn)的要快。但在面試中面試官往往希望看到你自己實(shí)現(xiàn)的版本。3. 字符串算法實(shí)戰(zhàn)應(yīng)用3.1 正則表達(dá)式引擎簡(jiǎn)化實(shí)現(xiàn)讓我們實(shí)現(xiàn)一個(gè)支持.和*的簡(jiǎn)化版正則表達(dá)式匹配def isMatch(text, pattern): memo {} def dp(i, j): if (i, j) not in memo: if j len(pattern): ans i len(text) else: first_match i len(text) and pattern[j] in {text[i], .} if j1 len(pattern) and pattern[j1] *: ans dp(i, j2) or (first_match and dp(i1, j)) else: ans first_match and dp(i1, j1) memo[i, j] ans return memo[i, j] return dp(0, 0)這個(gè)實(shí)現(xiàn)采用了動(dòng)態(tài)規(guī)劃加記憶化的方法時(shí)間復(fù)雜度O(TP)其中T和P分別是文本和模式的長(zhǎng)度。3.2 Trie樹的實(shí)際應(yīng)用Trie樹前綴樹是處理字符串集合的高效數(shù)據(jù)結(jié)構(gòu)class TrieNode: def __init__(self): self.children {} self.is_word False class Trie: def __init__(self): self.root TrieNode() def insert(self, word): node self.root for ch in word: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_word True def search(self, word): node self.root for ch in word: if ch not in node.children: return False node node.children[ch] return node.is_word def startsWith(self, prefix): node self.root for ch in prefix: if ch not in node.children: return False node node.children[ch] return TrueTrie樹在自動(dòng)補(bǔ)全、拼寫檢查、IP路由等場(chǎng)景中有廣泛應(yīng)用。比如在搜索框中輸入前綴時(shí)快速提示可能的關(guān)鍵詞。3.3 字符串壓縮算法對(duì)比Run-Length Encoding (RLE)def rle_compress(s): if not s: return res [] current s[0] count 1 for ch in s[1:]: if ch current: count 1 else: res.append(f{current}{count}) current ch count 1 res.append(f{current}{count}) compressed .join(res) return compressed if len(compressed) len(s) else sLZW壓縮算法簡(jiǎn)化版def lzw_compress(s): dictionary {chr(i): i for i in range(256)} next_code 256 result [] w for c in s: wc w c if wc in dictionary: w wc else: result.append(dictionary[w]) dictionary[wc] next_code next_code 1 w c if w: result.append(dictionary[w]) return result實(shí)際應(yīng)用建議對(duì)于短字符串壓縮可能反而增加長(zhǎng)度。建議先檢查原始字符串長(zhǎng)度再?zèng)Q定是否壓縮。在Python中對(duì)于簡(jiǎn)單場(chǎng)景內(nèi)置的zlib模塊通常就夠用了。4. 字符串算法優(yōu)化技巧4.1 滑動(dòng)窗口的三種變體滑動(dòng)窗口是解決子串/子數(shù)組問(wèn)題的利器主要有三種變體固定窗口大小def max_sum_subarray(arr, k): max_sum window_sum sum(arr[:k]) for i in range(len(arr) - k): window_sum window_sum - arr[i] arr[i k] max_sum max(max_sum, window_sum) return max_sum可變窗口大小求最小窗口def min_window(s, t): from collections import defaultdict target defaultdict(int) for ch in t: target[ch] 1 required len(target) formed 0 window_counts defaultdict(int) l, r 0, 0 ans float(inf), None, None while r len(s): ch s[r] window_counts[ch] 1 if ch in target and window_counts[ch] target[ch]: formed 1 while l r and formed required: if r - l 1 ans[0]: ans (r - l 1, l, r) ch s[l] window_counts[ch] - 1 if ch in target and window_counts[ch] target[ch]: formed - 1 l 1 r 1 return if ans[0] float(inf) else s[ans[1]:ans[2]1]可變窗口大小求最大窗口def longest_substring_with_k_distinct(s, k): from collections import defaultdict count defaultdict(int) max_len 0 l 0 for r, ch in enumerate(s): count[ch] 1 while len(count) k: left_char s[l] count[left_char] - 1 if count[left_char] 0: del count[left_char] l 1 max_len max(max_len, r - l 1) return max_len4.2 位運(yùn)算優(yōu)化技巧在處理小寫字母組成的字符串時(shí)可以用位運(yùn)算極大提升效率def check_unique_chars(s): checker 0 for ch in s: val ord(ch) - ord(a) if (checker (1 val)) 0: return False checker | (1 val) return True這個(gè)技巧還可以擴(kuò)展到其他場(chǎng)景比如判斷兩個(gè)字符串是否有公共字符def have_common_chars(s1, s2): mask1 mask2 0 for ch in s1: mask1 | 1 (ord(ch) - ord(a)) for ch in s2: mask2 | 1 (ord(ch) - ord(a)) return (mask1 mask2) ! 04.3 字符串哈希與滾動(dòng)哈希滾動(dòng)哈希是解決子串匹配、最長(zhǎng)回文子串等問(wèn)題的有力工具class RollingHash: def __init__(self, base256, mod10**97): self.base base self.mod mod self.powers [1] def get_hash(self, s): h 0 for ch in s: h (h * self.base ord(ch)) % self.mod return h def get_power(self, n): while len(self.powers) n: self.powers.append((self.powers[-1] * self.base) % self.mod) return self.powers[n] def update_hash(self, old_hash, old_char, new_char, length): power self.get_power(length - 1) new_hash (old_hash - ord(old_char) * power) % self.mod new_hash (new_hash * self.base ord(new_char)) % self.mod return new_hash使用示例rh RollingHash() s abcde h1 rh.get_hash(abc) # 前三個(gè)字符的hash h2 rh.update_hash(h1, a, d, 3) # 滑動(dòng)窗口后的hash (bcd) print(h2 rh.get_hash(bcd)) # True5. 字符串算法實(shí)戰(zhàn)問(wèn)題解析5.1 最長(zhǎng)無(wú)重復(fù)字符子串這是LeetCode上經(jīng)典的滑動(dòng)窗口問(wèn)題def lengthOfLongestSubstring(s): from collections import defaultdict char_map defaultdict(int) left max_len 0 for right, ch in enumerate(s): if ch in char_map: left max(left, char_map[ch] 1) char_map[ch] right max_len max(max_len, right - left 1) return max_len優(yōu)化版本使用數(shù)組代替哈希表當(dāng)字符集已知時(shí)更高效def lengthOfLongestSubstring(s): last_index [-1] * 128 # ASCII碼范圍 left max_len 0 for right, ch in enumerate(s): left max(left, last_index[ord(ch)] 1) last_index[ord(ch)] right max_len max(max_len, right - left 1) return max_len5.2 字符串的排列檢查判斷一個(gè)字符串是否是另一個(gè)字符串的排列子串def checkInclusion(s1, s2): from collections import defaultdict target defaultdict(int) window defaultdict(int) for ch in s1: target[ch] 1 left 0 matched 0 for right, ch in enumerate(s2): if ch in target: window[ch] 1 if window[ch] target[ch]: matched 1 while right - left 1 len(s1): if matched len(target): return True left_ch s2[left] if left_ch in target: if window[left_ch] target[left_ch]: matched - 1 window[left_ch] - 1 left 1 return False優(yōu)化版本使用數(shù)組代替哈希表def checkInclusion(s1, s2): if len(s1) len(s2): return False target [0] * 26 window [0] * 26 for ch in s1: target[ord(ch) - ord(a)] 1 for i in range(len(s1)): window[ord(s2[i]) - ord(a)] 1 if window target: return True for i in range(len(s1), len(s2)): window[ord(s2[i - len(s1)]) - ord(a)] - 1 window[ord(s2[i]) - ord(a)] 1 if window target: return True return False5.3 最小覆蓋子串這是滑動(dòng)窗口問(wèn)題的一個(gè)高級(jí)變種def minWindow(s, t): from collections import defaultdict target defaultdict(int) for ch in t: target[ch] 1 required len(target) formed 0 window_counts defaultdict(int) l 0 min_len float(inf) result for r, ch in enumerate(s): if ch in target: window_counts[ch] 1 if window_counts[ch] target[ch]: formed 1 while l r and formed required: if r - l 1 min_len: min_len r - l 1 result s[l:r1] left_char s[l] if left_char in target: window_counts[left_char] - 1 if window_counts[left_char] target[left_char]: formed - 1 l 1 return result性能分析這個(gè)算法的時(shí)間復(fù)雜度是O(|S| |T|)其中|S|和|T|分別是字符串s和t的長(zhǎng)度?？臻g復(fù)雜度是O(|T|)用于存儲(chǔ)目標(biāo)字符計(jì)數(shù)。