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