北京
字符串算法里有個經(jīng)典問題：給定一串字符，找出其中最長的回文子串。回文就是正讀反讀都一樣的序列，比如"madam"或"racecar"。子串則要求字符連續(xù)，"app"是"apple"的子串，"ale"卻不是。
這道題的限制條件很清晰：輸入只包含數(shù)字和英文字母，長度在1到1000之間。輸出要求返回最長回文子串本身，如果有多個答案，返回任意一個即可。比如輸入"babad"，"bab"和"aba"都是正確答案；輸入"cbbd"，則只能返回"bb"。
最直觀的暴力解法是枚舉所有子串，逐一檢查是否為回文。但子串?dāng)?shù)量是O(N2)，每次檢查又要O(N)，總復(fù)雜度達(dá)到O(N3)，對于長度1000的字符串顯然太慢。優(yōu)化的關(guān)鍵藏在回文的對稱性里。
觀察發(fā)現(xiàn)，任何回文都有一個中心點(diǎn)。奇數(shù)長度回文的中心是單個字符，比如"racecar"的'e'；偶數(shù)長度回文的中心在兩個字符之間，比如"abba"的兩個'b'中間。從這個中心向兩側(cè)擴(kuò)展，只要左右字符相等，回文就繼續(xù)增長。
基于這個洞察，"中心擴(kuò)展法"應(yīng)運(yùn)而生。具體做法是：遍歷字符串的每個位置，把它當(dāng)作奇數(shù)長度回文的中心，同時把它和下一個位置當(dāng)作偶數(shù)長度回文的中心，分別向兩邊擴(kuò)展。每次擴(kuò)展記錄找到的最長回文，最終答案就是所有記錄中的最大值。
實(shí)現(xiàn)時需要一個小技巧。寫一個輔助函數(shù)expand_around_center(s, left, right)，從給定的左右邊界開始向外擴(kuò)展：left左移，right右移，直到越界或字符不等為止。循環(huán)終止時，回文長度等于right - left - 1。對奇數(shù)情況調(diào)用(i, i)，偶數(shù)情況調(diào)用(i, i+1)，一次遍歷就能覆蓋所有可能的中心。
時間復(fù)雜度降到O(N2)，空間復(fù)雜度只有O(1)。對于面試場景，這個解法兼顧了效率和可解釋性——不需要動態(tài)規(guī)劃表，也不需要預(yù)處理，幾行代碼就能講清楚對稱擴(kuò)展的核心思想。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
