字符串這東西刷題前覺得“不就是字符數(shù)組嘛”刷題后才發(fā)現(xiàn)它才是算法面試里的“隱形大頭”。算法訓(xùn)練營Day8這一天正好把字符串Part01系統(tǒng)過了一遍反轉(zhuǎn)字符串、反轉(zhuǎn)字符串II、替換空格、翻轉(zhuǎn)字符串里的單詞、左旋轉(zhuǎn)字符串清一色高頻題。這篇就當一天的復(fù)盤筆記把思路、代碼、坑位一次說透給還在字符串門口打轉(zhuǎn)的朋友一個可直接照抄的路線。適合誰看準備面試的、剛刷完數(shù)組想進入字符串的、或者刷過幾道但總是死在邊界條件上的都可以對照著過一遍。我盡量用大白話把每一步講明白順便把當年踩過的坑標出來免得你重走彎路。1. 字符串在算法體系中的定位與學(xué)習(xí)路徑設(shè)計1.1 為什么單獨拿一整天講字符串很多人覺得字符串簡單無非是遍歷、比較、拼接。但真正刷起來才發(fā)現(xiàn)字符串是“數(shù)組的進階版”它既保留了數(shù)組的隨機訪問特性又疊加了字符編碼、不可變性、拼接性能這些額外約束所以面試官特別愛在字符串題目里藏邊界條件。訓(xùn)練營把字符串拆成Part01和Part02是有講究的。Part01聚焦“基礎(chǔ)操作”原地修改、雙指針、整體翻轉(zhuǎn)、局部翻轉(zhuǎn)這些都是后面KMP、滑動窗口、回文串等高級算法的基礎(chǔ)。如果Part01的地基沒打牢后面學(xué)KMP的next數(shù)組、學(xué)最長回文子串的動態(tài)規(guī)劃會學(xué)得懷疑人生。另外字符串在真實工作里出現(xiàn)頻率極高。無論是寫解析器、處理用戶輸入、做敏感信息脫敏還是寫接口層的參數(shù)校驗每天都會碰字符串。從面試角度說字符串題往往能在一道題里同時考察“編碼習(xí)慣”“邊界思維”“復(fù)雜度意識”三個維度性價比非常高。1.2 不同語言里字符串的底層差異是新手栽跟頭的第一站同樣一道字符串題用C寫和用Java寫、用Python寫處理方式完全不一樣。這里必須先把語言差異講清楚否則你會發(fā)現(xiàn)“我明明按照題解寫的怎么就是不對”。C里的std::string是可變對象底層是一段連續(xù)內(nèi)存本質(zhì)上是字符數(shù)組的封裝所以可以像數(shù)組一樣通過下標隨機訪問也可以原地修改。C風(fēng)格的字符串則以\0結(jié)尾面試中如果遇到C語言風(fēng)格的字符串題比如“字符串逆序輸出c”這種純C寫法必須手動維護結(jié)尾標志。Java的String是不可變對象每次拼接、替換都會生成新對象所以在Java里做字符串原地修改一般要轉(zhuǎn)成char[]或StringBuilder。這是新手特別容易踩的坑在Java里用String做循環(huán)拼接時間復(fù)雜度會退化到O(n2)因為每一次都會新建字符串對象。Python的str同樣是不可變對象而且Python沒有“字符數(shù)組”的概念字符串反轉(zhuǎn)最方便的是切片[::-1]但切片會生成新字符串。如果面試官要求“原地修改”Python就比較尷尬通常要轉(zhuǎn)成list操作再轉(zhuǎn)回字符串。刷題時我建議先選定一門主語言把思路跑通再用其他語言驗證一下對語言特性的理解。比如訓(xùn)練營里同一個小伙伴用C寫反轉(zhuǎn)字符串直接用swap即可我用Java寫就得先toCharArray()轉(zhuǎn)數(shù)組再交換字符最后new String(chars)轉(zhuǎn)回字符串。語言差異不是算法的核心但它是你寫出“能跑的代碼”的第一道門檻。注意算法訓(xùn)練營里我踩過最大的一個坑就是用Java的String直接做大量拼接然后超時。刷題之前先確認你的主語言對字符串的操作是不是原地修改這一點能省下一整晚的調(diào)試時間。2. 字符串題目實戰(zhàn)5道經(jīng)典題從暴力到優(yōu)雅2.1 反轉(zhuǎn)字符串344雙指針的入門教學(xué)這道題雖然簡單但它是字符串雙指針思想的“第一課”。題目要求輸入一個字符數(shù)組原地反轉(zhuǎn)不能額外開辟空間。暴力做法是新建一個等長數(shù)組倒序放進去。但面試官要的是原地修改這時候雙指針就是最優(yōu)解左指針從數(shù)組頭出發(fā)右指針從數(shù)組尾出發(fā)交換兩個指針指向的字符然后左指針右移、右指針左移直到兩個指針相遇。class Solution { public: void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } };如果有Java基礎(chǔ)注意要先轉(zhuǎn)成char[]Python的話雖然可以一行return s[::-1]但如果面試要求原地最好轉(zhuǎn)成list然后左右交換。為什么雙指針是最優(yōu)解因為它只遍歷一次時間復(fù)雜度O(n)空間復(fù)雜度O(1)。你可能會想“難道不能從中間開始往兩邊交換嗎”當然可以但中間向兩邊的寫法對奇數(shù)長度和偶數(shù)長度的處理更麻煩不如左右對撞簡單直觀。這道題我特別建議自己手寫一遍不是為了“會寫”而是為了體驗“while (left right)”這個條件的推導(dǎo)過程。很多人第一次寫會寫成while (left ! right)當字符數(shù)組長度是偶數(shù)時最終left會越過right永遠不等導(dǎo)致死循環(huán)或越界。left right才是嚴謹?shù)膶懛ā?.2 反轉(zhuǎn)字符串II541需求理解是最大考點這道題是反轉(zhuǎn)字符串的變種但難度陡增因為它加入了“每計數(shù)2k個字符就反轉(zhuǎn)前k個字符”的規(guī)則。題目要求是這樣的每計數(shù)至2k個字符就反轉(zhuǎn)這2k個字符中的前k個字符。如果剩余字符少于k個則將剩余字符全部反轉(zhuǎn)。如果剩余字符大于或等于k個但小于2k個則反轉(zhuǎn)前k個字符其余字符保持原樣。我第一次做這道題時直接用了一堆if-else去模擬結(jié)果寫了一堆bug。后來發(fā)現(xiàn)更優(yōu)雅的方式是讓for循環(huán)的步長直接設(shè)為2k這樣每次循環(huán)天然處在一個“2k區(qū)間”的起點。class Solution { public: string reverseStr(string s, int k) { for (int i 0; i s.size(); i 2 * k) { // 剩余字符小于 k反轉(zhuǎn)全部剩余 if (i k s.size()) { reverse(s.begin() i, s.end()); } else { // 剩余字符大于等于 k反轉(zhuǎn)前 k 個 reverse(s.begin() i, s.begin() i k); } } return s; } };這段代碼的思路核心在于“步長為2k”自動把字符串切成了若干個長度為2k的區(qū)間每個區(qū)間只需要判斷“當前位置加上k是否超過字符串長度”。如果超過說明剩余不足k個全反轉(zhuǎn)否則反轉(zhuǎn)前k個。兩個分支覆蓋了題目所有規(guī)則。這里最值得品的是為什么用i 2 * k而不是i。如果老老實實模擬“計數(shù)到2k才反轉(zhuǎn)”你得在循環(huán)里維護一個計數(shù)器代碼會復(fù)雜很多。而把步長設(shè)為2k就讓每次循環(huán)都站在一個區(qū)間的開頭問題就簡化成了“當前區(qū)間內(nèi)夠不夠k個”。2.3 替換空格劍指Offer 05從后往前填充的經(jīng)典思路題目要求把字符串中的每個空格替換成“%20”。這道題在訓(xùn)練營里被我們稱為“從后往前填充”思想的啟蒙題因為如果從前往后替換每次替換都要把后面的字符整體后移時間復(fù)雜度會退化成O(n2)。正確的做法分兩步先遍歷一遍原字符串統(tǒng)計空格數(shù)量計算出新字符串的總長度。假設(shè)原長度為len空格數(shù)為count新長度為len 2 * count因為一個空格從1個字符變成3個字符凈增2個字符。從后往前填充原字符串的末尾指針指向原長度-1的位置新字符串的末尾指針指向新長度-1的位置。從后往前遍歷原字符串遇到普通字符就復(fù)制到新末尾遇到空格就在新末尾依次填入“0”、“2”、“%”注意順序從后往前所以先填0再填2最后填%。class Solution { public: string replaceSpace(string s) { int count 0; for (char c : s) { if (c ) count; } int oldLen s.size(); int newLen oldLen 2 * count; s.resize(newLen); for (int i oldLen - 1, j newLen - 1; i 0; i--) { if (s[i] ) { s[j--] 0; s[j--] 2; s[j--] %; } else { s[j--] s[i]; } } return s; } };為什么從后往前填充是正確做法因為從后往前填充時每個字符最多被移動一次時間復(fù)雜度O(n)空間復(fù)雜度O(1)假設(shè)原字符串可變。這個過程類似于“歸并排序的合并階段從后往前放元素”的思路。一個常見的疑問是為什么不能先申請一個新數(shù)組遍歷原字符串拼出新結(jié)果當然可以但那樣空間復(fù)雜度是O(n)。在數(shù)組類題目里面試官往往要求“原地修改”從后往前填充就是為了滿足這個要求而設(shè)計的。3. 字符串進階實戰(zhàn)翻轉(zhuǎn)與旋轉(zhuǎn)3.1 翻轉(zhuǎn)字符串里的單詞151三步走策略這道題是字符串Part01里綜合難度最高的一道它把“移除多余空格”、“整體反轉(zhuǎn)”、“局部反轉(zhuǎn)”三個知識點串在一起。題目要求給定一個字符串逐個翻轉(zhuǎn)字符串中的每個單詞同時要去除多余空格。示例輸入是the sky is blue輸出blue is sky the輸入 hello world! 輸出world! hello。如果用高級語言自帶split比如Python的split()再反轉(zhuǎn)再join幾行就搞定了。但面試官通常希望你能手寫這個過程考察的是對字符串操作的控制力。標準的解法分三步第一步移除多余空格。這里的“多余”包括字符串開頭結(jié)尾的空格、單詞之間的多個空格?？梢杂每炻羔槍崿F(xiàn)快指針遍歷原字符串當快指針遇到一個單詞的起始字符時先把一個空格放到慢指針位置如果慢指針不在開頭然后把整個單詞復(fù)制過去。class Solution { public: string reverseWords(string s) { // 1. 移除多余空格 int slow 0; int n s.size(); for (int fast 0; fast n; fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast n s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow); // 2. 整體反轉(zhuǎn) reverse(s.begin(), s.end()); // 3. 逐個單詞反轉(zhuǎn) int start 0; for (int end 0; end s.size(); end) { if (end s.size() || s[end] ) { reverse(s.begin() start, s.begin() end); start end 1; } } return s; } };第二步把整個字符串反轉(zhuǎn)。以the sky is blue為例整體反轉(zhuǎn)后變成eulb si yks eht。這時每個單詞的字母順序是反的但單詞之間的相對順序已經(jīng)正確。第三步逐個單詞反轉(zhuǎn)。遍歷字符串遇到空格或到達末尾時把當前單詞區(qū)間反轉(zhuǎn)單詞內(nèi)部的字母順序就恢復(fù)正確了。此時eulb si yks eht變成blue is sky the恰好是答案。這個“先整體反轉(zhuǎn)再局部反轉(zhuǎn)”的思想特別重要它不僅能解決單詞翻轉(zhuǎn)還能解決后面要講的左旋轉(zhuǎn)字符串。核心邏輯是整體反轉(zhuǎn)解決的“順序”問題局部反轉(zhuǎn)解決的是“內(nèi)部順序”問題兩個操作合起來就能完成任意局部順序的調(diào)整。3.2 左旋轉(zhuǎn)字符串劍指Offer 58-II三次反轉(zhuǎn)搞定循環(huán)位移題目要求把字符串前面的k個字符轉(zhuǎn)移到字符串末尾。比如輸入abcdefgk2輸出cdefgab。暴力做法是新建一個字符串先拼后半部分再拼前半部分。但如果要求原地操作就要用到三次反轉(zhuǎn)的思路反轉(zhuǎn)前k個字符。反轉(zhuǎn)k到末尾的字符。反轉(zhuǎn)整個字符串。以abcdefgk2為例反轉(zhuǎn)前2個bacdefg。反轉(zhuǎn)剩余5個bagfedc。整體反轉(zhuǎn)cdefgab。寫成代碼非常簡單class Solution { public: string reverseLeftWords(string s, int n) { reverse(s.begin(), s.begin() n); reverse(s.begin() n, s.end()); reverse(s.begin(), s.end()); return s; } };為什么三次反轉(zhuǎn)能實現(xiàn)左旋本質(zhì)上字符串左旋轉(zhuǎn)等價于“把前半段和后半段交換位置但各自內(nèi)部順序保持不變”。第一次和第二次局部反轉(zhuǎn)讓前半段和后半段內(nèi)部的順序顛倒第三次整體反轉(zhuǎn)把所有字符的順序再顛倒一次于是每個段的內(nèi)部順序被“負負得正”恢復(fù)原樣而兩段之間的相對位置則完成了交換。這就像把兩疊牌各自翻面再把整疊牌翻面最終兩疊牌都回到了正面向上但位置互換了。這道題有一個變體右旋轉(zhuǎn)字符串比如LeetCode的“反轉(zhuǎn)字符串中的單詞III”和“輪轉(zhuǎn)數(shù)組”都有類似思路。如果你理解了三次反轉(zhuǎn)的本質(zhì)無論左旋還是右旋都能在三分鐘內(nèi)寫出來。提示左旋轉(zhuǎn)字符串用substr拼接也能做但面試時最好提一句“原地反轉(zhuǎn)方案”然后動手寫三次反轉(zhuǎn)。這能向面試官傳遞你理解復(fù)雜度的信號。4. 字符串高頻操作與底層細節(jié)從刷題到工程4.1 字符轉(zhuǎn)換、分割與大小寫面試?？嫉腁PI組合拳字符串Part01的算法題背后其實暴露了很多語言API的使用熟練度問題。訓(xùn)練營里我見過不少代碼邏輯正確但API用錯的案例這里把工程里高頻的幾類操作統(tǒng)一過一遍。字符串轉(zhuǎn)數(shù)字是絕對的高頻需求。C里可以用stoi、stol、stoll但要注意它們會拋出invalid_argument和out_of_range異常。Java里是Integer.parseInt和Long.parseLong同樣會拋NumberFormatException。真正面試時題目往往不會讓你直接調(diào)API而是要求手寫一個簡易的atoi這時候要考慮正負號、前導(dǎo)空格、溢出等問題。這一個考點可以單獨出一道中等題很多大廠都出過。字符串分割在工程里更常見。C沒有內(nèi)置的split需要配合istringstream和getline實現(xiàn)Java有String.split但要注意split的參數(shù)是正則表達式用.分割時要寫成split(\\.)Python的split()則好用很多但也要注意不傳參數(shù)和傳空格的區(qū)別。建議手寫一個通用的split函數(shù)放在自己的代碼模板里面試時直接背模板能省不少時間。大小寫轉(zhuǎn)換也是?？?。C里toupper和tolower接收的是int類型的字符碼返回int轉(zhuǎn)成char使用時經(jīng)常被忽略Java里Character.toUpperCase和Character.toLowerCasePython則是str.upper()和str.lower()。注意C的tolower如果傳入的是負數(shù)比如擴展ASCII碼是未定義行為需要先轉(zhuǎn)成unsigned char再調(diào)用。還有一個被很多人忽略的操作獲取子串。Java的substring(beginIndex, endIndex)是前閉后開區(qū)間Python的切片[start:end]也是前閉后開而C的substr(pos, count)第一個參數(shù)是起始位置第二個參數(shù)是長度。這三個語言三種語義我用Java寫習(xí)慣了切到C寫substr時就經(jīng)常把第二個參數(shù)寫成結(jié)束索引結(jié)果字符串長度比預(yù)期長或短。所有跨語言刷題的人都建議把這三個API的差異貼在顯示器上。4.2 調(diào)試字符串題的三個實用技巧打印、斷言、單步跑字符串題調(diào)試起來比數(shù)組題煩人因為它輸出出來是一長串字符很難一眼看出哪一位錯了。我在訓(xùn)練營里摸索出三個技巧能顯著減少調(diào)試時間。第一個技巧是打印時加輔助標記。不要直接cout s而是把字符一個個輸出并在每個字符下標處加上分隔符。比如調(diào)試反轉(zhuǎn)字符串時可以打印cout [ i ] s[i] 這樣能立刻定位到是哪個下標出了問題。特別是處理“翻轉(zhuǎn)字符串里的單詞”時空格在控制臺里很難肉眼分辨最好把空格替換成_再打印。第二個技巧是寫斷言驗證不變量。反轉(zhuǎn)字符串時最核心的不變量是“交換后左指針位置的值等于原來的右指針位置的值”?？梢栽诮粨Q之后加一個assert(s[left] oldRightValue s[right] oldLeftValue)如果斷言失敗說明指針移動順序?qū)戝e了。調(diào)試字符串題時斷言往往比看輸出更快。第三個技巧是準備一份“邊界測試用例集”。字符串題的邊界無非是空字符串、只含空格、首尾有空格、單詞之間多個空格、單個字符、全同字符。每道題寫完后把這些用例挨個跑一遍基本能覆蓋90%的隱藏bug。我在訓(xùn)練營里專門建了一個測試用例清單刷字符串時反復(fù)用效率高出不少。5. 常見問題與坑位記錄5.1 索引、邊界、空串字符串題的三座大山字符串Part01刷完我把周圍小伙伴問得最多的問題匯總了一下基本集中在三類第一類是索引越界。C里reverse(s.begin() i, s.begin() i k)如果i k超過s.end()雖然reverse不會崩但行為是未定義的。Java里substring更是直接拋IndexOutOfBoundsException。這類問題的根源在于“區(qū)間終點”和“區(qū)間長度”的概念沒分清。記住一條C的左閉右開區(qū)間和Java的substring左閉右開區(qū)間終點索引是可以等于末尾的但絕對不能超過末尾。第二類是空串和單字符的特殊處理。很多人在寫“翻轉(zhuǎn)字符串里的單詞”時都會在end s.size()這個條件上栽跟頭。如果字符串本身就是空串resize(0)后for循環(huán)條件end s.size()會怎么樣此時s.size()為0循環(huán)還是會執(zhí)行一次end 0然后start 1可能越界。所以遇到空串必須提前返回。第三類是C的resize與字符串長度的坑。resize(newLen)會把字符串擴長但擴長后新位置填充的是\0字符。如果你忘了從后往前填充而是從前往后遍歷那么遇到\0也會被當作普通字符處理結(jié)果就多出不可見字符。這種bug在控制臺輸出里很難發(fā)現(xiàn)但用size()打印長度時立刻露餡。5.2 字符串只是起點KMP與后續(xù)學(xué)習(xí)方向預(yù)告字符串Part01看起來只是反轉(zhuǎn)一下、替換一下但它背后延伸出去的算法很多。比如“判斷一個字符串是否是另一個字符串的子串”暴力做法是O(n*m)但用KMP算法可以把時間復(fù)雜度降到O(nm)。KMP的核心是next數(shù)組而next數(shù)組的構(gòu)建過程本質(zhì)上又是一次字符串匹配問題層層嵌套。再往后很多經(jīng)典算法都以字符串為基礎(chǔ)。比如文本搜索引擎里的BM25算法本質(zhì)上是計算查詢詞與文檔之間的相似度它需要大量的字符串切分和詞頻統(tǒng)計規(guī)則引擎Drools里的Rete算法雖然核心是模式匹配但匹配的前提也是把規(guī)則條件和事實對象轉(zhuǎn)成可比較的字符串特征甚至深度學(xué)習(xí)里的文本模型第一步也是把文本轉(zhuǎn)換成token序列。字符串處理能力強的人學(xué)這些算法會快得多。當然訓(xùn)練營的節(jié)奏是一步一步來的。Day8的Part01先把基礎(chǔ)操作練扎實Part02就會進入KMP、重復(fù)子串判斷等內(nèi)容。建議你把今天的五道題再獨立手寫一遍不要看題解寫不出來就重新看這一篇寫出來了再往后走。5.3 一些關(guān)于字符串刷題節(jié)奏的實戰(zhàn)建議最后分享幾個我自己調(diào)整過的刷題節(jié)奏適合那些刷了兩天字符串就開始懷疑人生的人。一天不要貪多。字符串Part01的五道題我第一天只做了反轉(zhuǎn)字符串和反轉(zhuǎn)字符串II第二天才做替換空格和翻轉(zhuǎn)字符串里的單詞第三天做左旋轉(zhuǎn)字符串并復(fù)盤。題目之間質(zhì)量差異很大比如“翻轉(zhuǎn)字符串里的單詞”一道題的思考量頂?shù)蒙先篮唵晤}給它留足時間完全值得。每道題寫完后不要立刻看下一題先做“復(fù)雜度三問”時間復(fù)雜度是多少空間復(fù)雜度是多少如果要優(yōu)化空間能不能做到O(1)這三個問題在面試時幾乎必問平時刷題就當成肌肉記憶來練。如果一道題看了15分鐘還是沒思路直接看題解但看完題解不要馬上抄而是合上題解自己在白紙上復(fù)盤一遍思路再動手寫。這一步習(xí)慣幫我把“看懂了”和“真的會了”區(qū)分開。注意字符串題最忌諱“裸寫”。哪怕你覺得思路已經(jīng)爛熟于心也一定先寫注釋或畫一下指針移動的過程。字符串的索引一旦錯了調(diào)試成本遠比數(shù)組題高因為字符輸出后很難用肉眼定位“誰在哪個位置被改錯了”。刷完這一天的內(nèi)容我最大的感受是字符串里沒有太多神秘的數(shù)據(jù)結(jié)構(gòu)知識它考的就是“你能不能把一件看似簡單的事情做到極致細節(jié)”。反轉(zhuǎn)字符串人人會寫但反轉(zhuǎn)字符串II一加邊界條件就刷掉了一批人。這其實也是算法面試的縮影不是比誰懂更多花哨的算法而是比誰能在邊界和細節(jié)上不出錯。我把Day8的題目和易錯點全寫在這篇里了如果你也刷到了字符串Part01建議跟著這五道題過一遍尤其注意每一次reverse的區(qū)間邊界。等Part02的KMP出來我再接著寫。