複習了一下第5題， 這篇文章Review一下思路和代碼
P0005
刷題地址:
https://leetcode.com/problems/longest-palindromic-substring/
簡單描述:
Given a string s, return the longest palindromic substring in s.
難度指數: Medium
這道題比較經典， 常規思路就是動態規劃， 時間複雜度偏高，題目的意思翻譯過來就是最長回文子字符串。也是字符串搜索的一個經典題目。
先貼代碼
public class Solution { public String longestPalindrome(String s) { if (s.isEmpty()) { return s; } int n = s.length(); boolean[][] dp = new boolean[n][n]; int maxLen = 1; int begin = 0; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { if (s.charAt(i) != s.charAt(j)) { dp[i][j] = false; } else { if (j - i < 3) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } }
if (dp[i][j] && (j - i + 1) > maxLen) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); }}因為是要返回最長回文子字符串， 所以需要確定起點和終點的位置，才能返回所需要的子串。
動態規劃，英文名叫Dynamic Programming。核心的要義是要確定狀態數組和狀態迭代中的推導關係。構造二維布爾類型數組， 行列對應起點和終點序號。 推導公式很明顯， 思路和代碼都比較清晰。
寫DP的時候時間複雜度基本不能達到最優， 比如這道題就是 O(n2)的時間複雜度， 因為計算狀態數組是二維的， 時間複雜度定死了。實際上我們在計算的過程中， 冥冥中會有一種感覺， 循環中的計算實際上感覺有點重複了。
這道題Wiki上面也是有記錄的:
https://en.wikipedia.org/wiki/Longest_palindromic_substring
使用馬拉車算法（Manacher's algorithm）可以達到線性複雜度， 效率上大大提升了。這個算法之後總結字符串中搜索的典型算法的時候總結一些， 這裡就不介紹了。刷題如果沒看過相關算法， 解法能達到線性複雜度的話，很好請收下我的膝蓋。
Golang代碼如下， 重寫的時候優化了一下內部的邏輯，代碼稍微比Java優雅一些。
func longestPalindrome(s string) string { if len(s) == 0 { return "" } dp := make([][]bool, len(s)) for i := range dp { dp[i] = make([]bool, len(s)) } left, length := 0, 1 for j := 0; j < len(s); j++ { dp[j][j] = true for i := 0; i < j; i++ { if j-i == 1 { dp[i][j] = s[i] == s[j] } else { dp[i][j] = s[i] == s[j] && dp[i+1][j-1] } if dp[i][j] && j-i+1 > length { length = j - i + 1 left = i } } } return s[left : left+length]}