讨论/《中级算法》 - 最长回文子串/
《中级算法》 - 最长回文子串
共 11 个回复

c++, 双指针,从中间开始计算回文子串的长度

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() <= 1)
            return s;
        int maxLenStart = 0, maxLen = 1;
        int mid = 0;
        while (mid < s.size()) {
            int midBegin = mid;
            int midEnd = mid;
            while (midEnd+1 < s.size() && s[midEnd] == s[midEnd+1]) midEnd++;
            
            mid = midEnd + 1;
            
            int left = midBegin, right = midEnd;
            while (left-1 >= 0 && right+1 < s.size() && s[left-1] == s[right+1]) {
                left--;
                right++;
            }
            
            int cur_len = right - left + 1;
            if (cur_len > maxLen) {
                maxLen = cur_len;
                maxLenStart = left;
            }
        }
        return s.substr(maxLenStart, maxLen);
    }
};
5

简单思路,直接超时

image_48.png

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        int max = 0;
        String result = "";
        for (int i = 0; i < length; i++) {
            for (int j = i; j <= length; j++) {
                // 如果当前是回文串,记录结果和当前最大值
                if(palindrome(s.substring(i,j))){
                    if(max < j - i + 1){
                        max = j - i + 1;
                        result = s.substring(i,j);
                    }
                }
            }
        }
        return result;
    }
    // 判断字符串是否是回文串
    boolean palindrome(String s){
        int length = s.length();
        if(length == 0){
            return false;
        }
        // 首尾比较,不相等,直接返回false
        for (int i = 0; i < length / 2; i++) {
            if(s.charAt(i) != s.charAt(length - i -1)){
                return false;
            }
        }
        return true;
    }
}
2

1、暴力遍历,很多重复的字符作为起点被重复计算,对重复字符进行优化可以节省耗时,空间复杂度O(1)
2、使用DP

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() <= 1) return s;
        int begin = 0, len = 1;
        for (int i = 0; i < s.size() - 1; ++i) {
            for (int j = i; j < s.size(); ++j) {
                while (j + 1 < s.size() && s[j] == s[j + 1]) j++;
                int left = i, right = j;
                while (left - 1 >= 0 && right+1 < s.size() && s[left - 1] == s[right + 1]) {
                    left--;
                    right++;
                }
                if (right - left + 1 > len) {
                    len = right - left + 1;
                    begin = left;
                }
                i = j + 1;
            }
        }
        return s.substr(begin, len);
    }
};

image.png

2、DP

class Solution {
public:
    // DP 状态:DP[i][j] = true || false, 表示i 到 j是否是回文串
    // DP[i][j] = if (s[i] != s[j]) 0 else DP[i+1][j-1]
    // 边界 DP[i][i] = 1, dp[i][i+1] = (s[i]==s[i+1]) ? 1:0
    string longestPalindrome(string s) {
        if (s.size() <= 1) return s;
        int begin = 0, len = 0;
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size()));
        for (int right = 0; right < s.size(); ++right) {
            for (int left = 0; left <= right; ++left) {
                if (s[left] != s[right]) {
                    dp[left][right] = false;
                } else {
                    if (right - left < 3) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }
                if (dp[left][right] && right - left + 1 > len) {
                    begin = left;
                    len = right - left + 1;
                }
            }
        }
        return s.substr(begin, len);
    }
};

image.png

这是C++;
我的python有一个常见的错误:

a = [[0] * N] * N
# 这个会导致地址共享,相当于,每一行都是相同的list

# 分开写就很显然了

b = [0] * N 
# 这个是OK的,

c = [b] * N
# 显然就有问题了

然后简单解读下所谓动态规划的解法, 简化一下

f(x : 开始的位置, L: 步长)= 1 , 比如 “010" a(0,0) = a(1,0) = a(2,0) = 1 每个字符与相隔0的字符相等。

然后一个关系是:
if f(x ,L) = 1 <==> f(x+1, L-2) = 1 并且 s[x] == s[x+L] (当L >= 1)

每 “一个 回文字符串 开始位置为x , 长度为 L (L>=1)” , 等价于 (开始位置为x+1,长度为L-1的字符串是回文,且,位置 x and x+L 的两个字符相同)

这是什么语言呀,我简单用python逐字码进去,答案不对呀,这个a怎么理解,状态是什么


def longestPalindrome(s):
    N = len(s)
    
    if(N == 0): return ""
    if(N == 1): return s
    
    a = [[0] * N] * N
    
    ans = s[0]
    
    for j in range(0,N):
        for k in range(0, N - j):
            if s[k] == s[j+k] and (j <= 1 or a[k+1][j+k-1]==1):
                a[k][j+k] = 1
                if j+1 > len(ans):
                    ans = s[k:k+j+1]
                    
    return ans
    
    

简单解读一下,就是“11234321” , 设置一个mid 指针,mid指针从左向右移动,(同时跳过连续相等的字符为了比如“1221”这种情况),然后mid指针每向右边移动一次,同时向左和右边发射 mid_left, mid_right 指针,判断mid左右两侧的字符是否关于mid对称,然后直到不对称为止,即我们可以记录一次回文的长度,最后输出最长的。

好快啊!奈何看不懂。。

动态规划,人人都能学会
双50%

class Solution {
public:
    string longestPalindrome(string s) {
        int size=s.size();
        if(size==1) return s;
        vector<vector<bool>> myvc(size,vector(size,false));
        //首位一致表示只有一个char,肯定是回文的
        for(int i=0;i<size;i++)
        {
            myvc[i][i]=1;
        }
        //记录最大长度及对应起始位置
        int length=1;
        int pos=0;
        //i,左边界递减,因为左边的值需要右边的判断结果
        for(int i=size-1;i>=0;i--)
        {
            //j,右边界递增,因为右边的计算结果需要依赖左边的判断结果
            for(int j=i+1;j<size;j++)
            {
                //如果相邻,直接判断是不是相等
                if(j-i==1)
                {
                    if(s[i]==s[j])
                    {
                        myvc[i][j]=1;
                        if(length<2)
                        {
                            length=2;
                            pos=i;
                        }
                    }
                    else
                    {
                        myvc[i][j]=0;
                    }
                }
                else//如果位置相差两个以上,结合之前的判断进行状态转换
                {
                    if(s[j]==s[i]&&myvc[i+1][j-1])
                    //这里看出之前的for第增递减依赖顺序
                    {
                        myvc[i][j]=1;
                        if(j-i+1>length)
                        {
                            length=j-i+1;
                            pos=i;
                        }
                    }
                    else
                    {
                        myvc[i][j]=0;
                    }
                }
            }
        }
        string ans(s,pos,length);
        return ans;
    }
};

暴力破解加一点小小的优化,刚好能过,超越5%,运行1300毫秒,哈哈哈哈

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        int maxLen = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = i; j < n; ++j) {
                //如果长度没有现在已经得到的长,就不用再算了
                if(j + 1 - i <= maxLen) {
                    continue;
                }
                if(is(s.substring(i, j + 1))) {
                    maxLen = j - i + 1;
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
    public boolean is(String str) {
        int n = str.length();
        int l = 0, r = n - 1;
        while(l < r) {
            if(str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l += 1;
            r -= 1;
        }
        return true;
    }
}

java 代码

时间复杂度为n,将回文串分为奇数偶数
奇数遍历的时候以每个字符为中心
偶数遍历的时候以每个字符与其相邻的字符为中心

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==0){
            return s;
        }
        int sum=1; 
        int len;
        int ll=0;
        int rr=0;

        for(int i=0;i<s.length();i++){
            int l=i-1;
            int r = i+1;
            //奇数的回文串
            while(( l>=0 && r<s.length())&&(s.charAt(l)==s.charAt(r))){
                len = r-l+1;
                if(len>sum){
                    sum=len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }
            //偶数回文串
            l=i;
            r=i+1;
            while(( l>=0 && r<s.length())&&(s.charAt(l)==s.charAt(r))){
                len = r-l+1;
                if(len>sum){
                    sum=len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }
        }
        return s.substring(ll,rr+1);
    }
}