[leetcode题解]05.Longest Palindromic Substring

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 的最大长度为1000。

示例 1:

输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案。

示例 2:

输入: "cbbd" 输出: "bb"

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 的最大长度为1000。

示例 1:

输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案。

示例 2:

输入: “cbbd” 输出: “bb”

思路:遍历所有长度的子串,确定是否为回文串,如果为回文串就判断长度是否大于最大值,如果大于最大值,就要更新记录最大回文子串的相关信息。

所有长度为1的子串均是回文串,所以我们从长度为2的子串开始判断就可以了,这里判断长度为n的子串我们只需要判断其内部长度为n-2的子串是否为回文串,并且,当前子串头尾字符是否相等即可。我们用dp[i][j]来记录从i到j的子串是否是回文串,aba为回文串,那么xabax一定是回文串,所以我们判断i到j是否是回文串,只需要s[i]等于s[j]且dp[i + 1][j-1]为回文串即可。为了方便处理,我们初始把dp全部初始为true即可。

c语言代码如下:

#define N 1024

char* longestPalindrome(char* s) {
    bool dp[N][N];
    int maxlen = 1;
    /*ple recored the left pos, and pri record the right pos of the max palindromic substring*/
    int ple = 0, pri = 0;
    int pos = 0, gap = 0;
    int len = strlen(s);
    
    /*if s[i]-s[j] is palindromic, then the dp[i][j] is true, otherwise is false*/
    memset(dp, -1, sizeof(dp));
    
    for (gap = 1; gap < len; gap++) {
        for (pos = 0; pos + gap < len; pos++) {
            if (s[pos] == s[pos + gap] && dp[pos + 1][pos + gap - 1]) {
                    dp[pos][pos + gap] = true;
                    if (gap + 1 > maxlen) {
                        maxlen = gap + 1;
                        ple = pos;
                        pri = pos + gap;
                    }
            } else {
                dp[pos][pos + gap] = false;
            }
        }
    }
    s[pri + 1] = '\0';
    return (s + ple);
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]05.Longest Palindromic Substring

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/179.html

相关文章