專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友在入職之前遇到公司背調，問的還那么詳細，關鍵被問的人還那么配合。我覺得招一個產品經理不至于，又不是啥高管。之前我找工作的時候也遇到過背調，不過查的是社保記錄，主要是判斷工作履歷是否真實，是否真的在那家公司干過，個人能力是查不到的。

背調現在也是屢見不鮮，之前有一個同事離職之后空閑了半年多，背調的時候填我的手機號，臨時給我打電話告訴我該怎么說，結果不到10分鐘hr真打過來了，其實這種背調就是往好的夸，最后也成功入職，所以大家在工作中最好要有一個玩的特別好的同事，以后找工作遇到背調可以幫你說兩句。但有的人離職是因為和領導關系搞的不好，有的背調公司要填領導的聯系方式，這種背調就很坑了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第5題：最長回文子串。

問題描述

來源：LeetCode第5題

難度：中等

給你一個字符串 s，找到 s 中最長的回文子串。如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。

示例1：

輸入：s = "babad" 輸出："bab" 解釋："aba" 同樣是符合題意的答案。

示例2：

輸入：s = "cbbd" 輸出："bb"

• 1 <= s.length <= 1000

• s 僅由數字和英文字母組成

問題分析

這題是讓找出字符串 s 的最長回文子串， 最簡單的一種解決方式就是截取字符串 s 的所有子串 ，然后判斷它的所有子串哪些是回文串，保存最長的回文串即可，這種解法雖然簡單，但時間復雜度比較高。

還一種解決方式就是中心擴散法 ，我們需要以每一個字符為中心往兩邊擴散，查找并記錄最長的回文子串。查找完之后下一步我們還要以下一個字符為中心往兩邊擴散進行查找，這樣效率也不是很高。這個時候我們可以對他進行優化，使用馬拉車算法。

所以這題的最經典解法還是 馬拉車算法 ，關于馬拉車算法大家可以看下 中第 13 章的13.2 馬拉車算法，這里就不在介紹。我們這里主要講另外一種解決方式，動態規劃。

我們定義二維數組dp[][]，如果dp[left][right]為true，則表示子串s[left,right]是回文子串，如果dp[left][right]為false，則表示子串s[left,right]不是回文子串。

如果dp[left][right]是回文子串，首先dp[left+1][right-1]必須是回文子串，并且s[left]和s[right]也必須相等，如下圖所示。

1，如果s[left]!=s[right]，子串s[left,right]不可能是回文子串。

2，如果s[left]==s[right]，子串s[left,right]能不能構成回文子串還需要進一步判斷：

2.1，如果left==right，也就是說只有一個字符，我們認為它是回文子串。即dp[left][right]=true（left==right）

2.2，如果right-left<=2，類似于"aa"，或者"aba"，中間最多只有一個字符，我們也認為它是回文子串，即dp[left][right]=true（right-left<=2）

2.3，如果right-left>2，需要判斷dp[left+1][right-1]是否是回文子串，才能確定dp[left][right]是否為true還是false。即dp[left][right]=dp[left+1][right-1]

所以我們可以找出遞推公式如下：

dp[left][right]=s[left]==s.[right]&&dp[left+1][right-1]

這里要注意，因為dp[left][right]的值要依賴dp[left+1][right-1]的值，所以不能從上到下一行一行的遍歷。因為在二維網格中dp[left+1][right-1]是在dp[left][right]的下一行，所以必須先計算dp[left+1][right-1]的值，才能計算dp[left][right]。

遍歷方式有多種，可以從左到右一列一列的遍歷，也可以從下到上一行一行的遍歷，還可以從對角線往右上角一行一行的遍歷， 無論哪種方式，都要保證在計算dp[left][right]的時候，dp[left+1][right-1]的值一定是計算過的 。

JAVA：

public String longestPalindrome(String s) {
    // start表示最長回文子串開始的位置，為了后面截取。
    // maxLen表示最長回文子串的長度
    int start = 0, maxLen = 1;
    int length = s.length();
    boolean[][] dp = new boolean[length][length];
    for (int right = 1; right < length; right++) {
        for (int left = 0; left < right; left++) {
            // 如果兩種字符不相同，肯定不能構成回文子串。
            if (s.charAt(left) != s.charAt(right))
                continue;
            // 下面是s[left]和s[right]兩個字符相同情況下的判斷。
            if (right - left <= 2) {
                // 類似于"a"，"aa"和"aba"，也是回文子串。
                dp[left][right] = true;
            } else {
                // 類似于"a******a"，要判斷他是否是回文子串，只需要
                // 判斷"******"是否是回文子串即可。
                dp[left][right] = dp[left + 1][right - 1];
            }
            // 如果字符串從left到right是回文子串，保存最長的回文子串。
            if (dp[left][right] && right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
        }
    }
    // 截取最長的回文子串
    return s.substring(start, start + maxLen);
}

C++：

public:
    string longestPalindrome(string s) {
        // start表示最長回文子串開始的位置，為了后面截取。
        // maxLen表示最長回文子串的長度
        int start = 0, maxLen = 1;
        int length = s.size();
        vector
         

 int>> dp(length, vector< 
int>(length)); 

         
for ( 
int right =  
1; right < length; right++) { 

             
for ( 
int left =  
0; left < right; left++) { 

                 
// 如果兩種字符不相同，肯定不能構成回文子串。 

                 
if (s[left] != s[right]) 

                     
continue; 

                 
// 下面是s[left]和s[right]兩個字符相同情況下的判斷。 

                 
if (right - left <=  
2) { 

                     
// 類似于"a"，"aa"和"aba"，也是回文子串。 

                    dp[left][right] =  
true; 

                }  
else { 

                     
// 類似于"a******a"，要判斷他是否是回文子串，只需要 

                     
// 判斷"******"是否是回文子串即可。 

                    dp[left][right] = dp[left +  
1][right -  
1]; 

                } 

                 
// 如果字符串從left到right是回文子串，保存最長的回文子串。 

                 
if (dp[left][right] && right - left +  
1 > maxLen) { 

                    maxLen = right - left +  
1; 

                    start = left; 

                } 

            } 

        } 

         
// 截取最長的回文子串 

         
return s.substr(start, maxLen); 

    } 

 

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。