首页 > 其他 > 详细

#5 Longest Palindromic Substring

时间:2015-04-07 21:29:35      阅读:104      评论:0      收藏:0      [点我收藏+]

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[i]==s[j],那么s[i+1]==s[j-1]时,才是子串。时间复杂度O(n2)。

代码如下:

string longestPalindrome(string s) {
    int n = s.size();
    int substrBegin = 0;
    int maxlen = 1;
    bool state[1000][1000] = { false };
    for (int i = 0; i < n; i++){
        state[i][i] = true;
        if (i < n - 1 && s[i] == s[i + 1]){
            state[i][i + 1] = true;
            substrBegin = i;
            maxlen = 2;
        }
    }
    for (int i = 3; i <= n ; i++){
        for (int j = 0; j < n - i + 1; j++){
            if (s[j] == s[j + i - 1] && state[j + 1] [j+i-2]== true){
                state[j][j+i - 1] = true;
                substrBegin = j;
                maxlen = i;
            }
        }
    }
    return s.substr(substrBegin, maxlen);
}

 

#5 Longest Palindromic Substring

原文:http://www.cnblogs.com/Scorpio989/p/4399328.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!