欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长回文子串

程序员文章站 2024-02-27 17:59:51
...

给定字符串s,找到字符串中最长的回文子串。假设s最大长度1000。

回文子串指正向读与反向读一致的子串。

要求输出 子串长度 与 子串本身。

方法有很多。 

选择采用动态规划,效率并不高。

大致思路记录:

if 头尾字符相同 

最长子序列长度 = Max(去掉首部的最长子序列长度,去掉尾部的最长子序列长度,去掉首尾的最长子序列长度);

if 头尾字符不同

最长子序列长度 = Max(去掉首部的最长子序列长度,去掉尾部的最长子序列长度);

细节:

头尾字符相同时,

if 子序列为连续的最长子序列           最长子序列长度 = 去掉首尾的最长子序列长度+2

if子序列不连续                                  最长子序列长度 = 去掉首尾的最长子序列长度

然后去与 去掉首部的最长子序列长度,去掉尾部的最长子序列长度 取最大值

 

class Solution {
    public String longestPalindrome(String str) {
        int[][] d = new int[1000][1000];//存最大回文子串长度
    	int maxlen = 0;int low = 0,high = 0;
    	int len = str.length();

        if(len==0||str==null||str==""){return str;}
        
    	for(int i=len-1;i>=0;i--) {
    		d[i][i]=1;
    		for(int j=i+1;j<len;j++) {
    			if(str.charAt(i)==str.charAt(j)) {

    				if(d[i+1][j-1]!=(j-1)-(i+1)+1) {//必须为连续子串才+2,求出削减首尾的值
    					d[i][j]=d[i+1][j-1];
    				}else {
    					d[i][j]=d[i+1][j-1]+2;//子串必须为连续子串才+首尾2个字符
    				}
                    
    				int tmp = Math.max(d[i+1][j], d[i][j-1]);//比较三种情况的最大值:削减首部、削减首尾、削减尾部
                    
    				d[i][j]=Math.max(d[i][j], tmp);
    				
    			}else {
    				d[i][j]=Math.max(d[i+1][j], d[i][j-1]);
    			}
 
    		}
    	}
        
        for(int i=0;i<len;i++) {
    		for(int j=i+1;j<len;j++) {
    			if(j-i+1==d[i][j]&&d[i][j]>maxlen) {//寻找最长连续子串的位置
    				maxlen=d[i][j];
    				low=i;
    				high=j;
    			}
    		}
    	}
    
    	
    	
		return str.substring(low, high+1);
    }
}