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

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

好快啊!奈何看不懂。。

动态规划,人人都能学会
双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);
    }
}

动态规划一步到位。s.substr的时间复杂度蛮高的,不要随便扔上,能加条件就加条件。

class Solution {
public:
    string longestPalindrome(string s) {
    if(s.size()==0) return "";
    if(s.size()==1) return s;
    int n=s.size();
    vector<vector<int>> a(n,vector<int>(n,0));
    string ans="";
    ans+=s[0];
    
    for(int j = 0;j<s.size();++j)
    {
        for(int k=0;k+j<s.size();++k)
          {
              if(s[k]==s[j+k] && (j<=1||a[k+1][j+k-1]==1))
               {
                  a[k][j+k]=1;
                 if(j+1>ans.size()) ans=s.substr(k,j+1);
               }  
          }
    } 
    return ans;
    }
};