1. 字符串算法專題深度解析字符串處理是算法領(lǐng)域的核心基礎(chǔ)也是各大技術(shù)面試中的高頻考點。今天咱們來聊聊字符串專題中的幾個硬核知識點這些都是我在算法訓(xùn)練和實際工程中總結(jié)的實戰(zhàn)經(jīng)驗。字符串算法看似簡單但想要寫出高效、優(yōu)雅的解決方案需要掌握一些關(guān)鍵技巧和思維模式。特別是當(dāng)處理大規(guī)模文本數(shù)據(jù)時算法效率的差異會導(dǎo)致性能上的天壤之別。下面我就結(jié)合幾個典型問題帶大家深入理解字符串處理的精髓。提示建議在閱讀本文時準(zhǔn)備好紙筆跟著示例手動模擬算法執(zhí)行過程這種手推方法能幫你真正理解算法本質(zhì)。1.1 字符串匹配的三種境界字符串匹配問題可以說是算法界的Hello World但不同解法之間的效率差異可能達到百萬倍。我們來看三種典型的解決方案暴力匹配法- 時間復(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算法- 時間復(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算法- 實踐中最快的單模式匹配算法Boyer-Moore算法采用了從右向左比較的策略并利用壞字符規(guī)則和好后綴規(guī)則實現(xiàn)跳躍式匹配在真實場景中往往能達到亞線性時間復(fù)雜度。避坑指南KMP算法雖然理論復(fù)雜度優(yōu)秀但在實際應(yīng)用中由于預(yù)處理開銷和緩存不友好等問題對于短模式串(長度10)可能還不如暴力法快。要根據(jù)具體場景選擇合適的算法。1.2 回文串處理的奇偶陷阱回文串問題是字符串專題中的另一個經(jīng)典類別?？此坪唵蔚膯栴}背后隱藏著不少陷阱# 中心擴展法 - 處理奇偶回文的統(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ù)長度 tmp expand(i, i) if len(tmp) len(res): res tmp # 偶數(shù)長度 tmp expand(i, i1) if len(tmp) len(res): res tmp return res這個解法巧妙之處在于通過中心擴展統(tǒng)一處理了奇偶兩種情況。在實際編碼面試中很多候選人會忽略偶數(shù)長度回文的情況導(dǎo)致解決方案不完整。1.3 字符串翻轉(zhuǎn)的六種姿勢字符串翻轉(zhuǎn)看似簡單但不同的實現(xiàn)方式反映了不同的編程思維使用切片Pythonic方式s hello print(s[::-1]) # olleh使用reversed函數(shù)s hello print(.join(reversed(s))) # olleh雙指針法適用于不能使用庫函數(shù)的場景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遞歸法不推薦實際使用教學(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性能實測在Python中切片法[::-1]是最快的比雙指針法快3-5倍。但在C等語言中雙指針原地交換才是最優(yōu)解。2. 字符串編碼與轉(zhuǎn)換技巧2.1 Unicode與編碼陷阱處理多語言文本時編碼問題是個大坑。來看幾個常見問題及解決方案計算實際字符數(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 (錯誤方法) print(len(s.encode(utf-16-le))//2) # 7 (錯誤方法) # 正確方法 import unicodedata print(unicodedata.normalize(NFC, s)) # 標(biāo)準(zhǔn)化 print(len(unicodedata.normalize(NFC, s))) # 5處理特殊字符# 過濾控制字符 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)化這類問題在算法競賽和面試中經(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)化通常比自己實現(xiàn)的要快。但在面試中面試官往往希望看到你自己實現(xiàn)的版本。3. 字符串算法實戰(zhàn)應(yīng)用3.1 正則表達式引擎簡化實現(xiàn)讓我們實現(xiàn)一個支持.和*的簡化版正則表達式匹配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)這個實現(xiàn)采用了動態(tài)規(guī)劃加記憶化的方法時間復(fù)雜度O(TP)其中T和P分別是文本和模式的長度。3.2 Trie樹的實際應(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樹在自動補全、拼寫檢查、IP路由等場景中有廣泛應(yīng)用。比如在搜索框中輸入前綴時快速提示可能的關(guān)鍵詞。3.3 字符串壓縮算法對比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壓縮算法簡化版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實際應(yīng)用建議對于短字符串壓縮可能反而增加長度。建議先檢查原始字符串長度再決定是否壓縮。在Python中對于簡單場景內(nèi)置的zlib模塊通常就夠用了。4. 字符串算法優(yōu)化技巧4.1 滑動窗口的三種變體滑動窗口是解決子串/子數(shù)組問題的利器主要有三種變體固定窗口大小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ōu)化技巧在處理小寫字母組成的字符串時可以用位運算極大提升效率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這個技巧還可以擴展到其他場景比如判斷兩個字符串是否有公共字符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 字符串哈希與滾動哈希滾動哈希是解決子串匹配、最長回文子串等問題的有力工具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) # 前三個字符的hash h2 rh.update_hash(h1, a, d, 3) # 滑動窗口后的hash (bcd) print(h2 rh.get_hash(bcd)) # True5. 字符串算法實戰(zhàn)問題解析5.1 最長無重復(fù)字符子串這是LeetCode上經(jīng)典的滑動窗口問題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)字符集已知時更高效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 字符串的排列檢查判斷一個字符串是否是另一個字符串的排列子串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 最小覆蓋子串這是滑動窗口問題的一個高級變種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性能分析這個算法的時間復(fù)雜度是O(|S| |T|)其中|S|和|T|分別是字符串s和t的長度?？臻g復(fù)雜度是O(|T|)用于存儲目標(biāo)字符計數(shù)。