程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [C++]LeetCode: 99 Longest Palindromic Substring (最長回文子串)

[C++]LeetCode: 99 Longest Palindromic Substring (最長回文子串)

編輯:關於C++

題目:Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路:題目要求的s的一個最長回文子串。暴力解決辦法就是枚舉所有的子串,再對每個子串進行回文判斷。進行剪枝,我們考慮可以使用動態規劃來避免重復的判斷。

 

dp[i][j]表示s[i...j]是否是回文.初始化:dp[i][i] = true ( 0 <= i <= n-1) ; dp[i][i-1] = true (1 <= i <= n-1); 其余的初始化為false根據回文的規則,判定s[i...j] 是否是回文,如果是,需要s[i] == s[j] 並且dp[i+1][j-1] == true 。即遞推公式:dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true) Attention: 1. 其他值初始化為false , 利用memset最初把所有值初始化false.
//dp[i][j]表示子串s[i...j]是否是回文
        bool dp[len][len];
        memset(dp, 0, sizeof(dp));
2. 初始化時需要初始化dp[i][i] 和dp[i][i-1]。第二個容易遺忘,但是後面會用到。
 dp[0][0] = true;
        for(int i = 1; i < len; i++)
        {
            dp[i][i] = true;
            dp[i][i-1] = true;  //容易遺忘的初始化,k = 2時,dp[i+1][i+k-2]要用到
        }
3. 題目要求返回最長的回文子串,所以我們要維護兩個變量,一個是最長回文的起點,還有它的長度。
 if(longlen < k)
                    {
                       retleft = i;
                       longlen = k;
                    }
4. 要想窮舉所有情況,我們外層循環枚舉所有的子字符串長度,內層循環枚舉字符串的所有起始位置。
for(int k = 2; k <= len; k++)   //枚舉子字符串的長度
        {
            for(int i = 0; i <= len - k; i++)  //枚舉子字符串的起始位置
復雜度:O(N^2) AC Code:
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        const int len = s.size();
        //dp[i][j]表示子串s[i...j]是否是回文
        bool dp[len][len];
        memset(dp, 0, sizeof(dp));
        
        //最長回文的起點和長度
        int retleft = 0;
        int longlen = 1;
        
        dp[0][0] = true;
        for(int i = 1; i < len; i++)
        {
            dp[i][i] = true;
            dp[i][i-1] = true;  //容易遺忘的初始化,k = 2時,dp[i+1][i+k-2]要用到
        }
        
        for(int k = 2; k <= len; k++)   //枚舉子字符串的長度
        {
            for(int i = 0; i <= len - k; i++)  //枚舉子字符串的起始位置
            {
                if(s[i] == s[i+k-1] && dp[i+1][i+k-2])
                {
                    dp[i][i+k-1] = true;
                    if(longlen < k)
                    {
                       retleft = i;
                       longlen = k;
                    }
                }
            }
        }
        
        return s.substr(retleft, longlen);
    }
};

這道題還有一個O(N)復雜度的解法:最長連續回文串(Longest Palindromic Substring)、

 





 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved