[leetcode]5. Longest Palindromic Substring最长回文子串

青旅半醒 2021-09-28 09:30 280阅读 0赞

### 最长回文子串 ###

*   *  思想
     *  代码
     *  结果
     *  改进
     *   *  DP的改进
         *  巧妙的方法：从中心扩展
     *  Manacher’s Algorithm (O(n))
     *  总结

## 思想 ##

这道题是 DP 下的题目，找一个字符串中最长的回文子串。  
首先要解决判别回文子串的问题。  
其次，利用DP的思想：

把**字符串的长度**作为分解子问题的标准

长度为N的字符串的最大回文子串长度  
= max\{ 长度为N-1的最大回文子串长度 , 加入第N个字符之后从右往左数最长回文串的长度\}

## 代码 ##

bool judge(char*a,int right);
    
    class Solution { 
    public:
       string longestPalindrome(string s) { 
           if(s==""){ 
               return "";   
           }
       	int len=s.size();
       	int size[1010];
       	string ret[1010];
       	
       	memset(size,0,sizeof(size));
       	//初始化
       	size[0]=1;
       	ret[0]=s[0];
       	
       	 
       	for(int i=1;i<len;i++){ 
       		//对于新添进来的串，看是否长度增加 
       		for(int j=0;j<i+1-size[i-1];j++){ 
       			if(judge( &(s[j]),i-j)){ 
       				size[i]=i-j+1;
       				ret[i]=s.substr(j,i-j+1);
       				break;
       			}
       		}	
       		
       		if(!size[i]){ 
       			size[i]=size[i-1];
       			ret[i]=ret[i-1];
       		}
       	}
       	
       	return ret[len-1];
       }
    };
    
    
    //判断a是否是回文串 
    bool judge(char*a,int right){ 
       int i,j;
       
       for(i=0,j=right;i<j;i++,j--){ 
       	if(a[i]!=a[j]) return false;
       } 
       
       return true;
    }

## 结果 ##

> Runtime: 212 ms, faster than 25.38% of C++ online submissions for Longest Palindromic Substring.

> Memory Usage: 18.8 MB, less than 39.81% of C++ online submissions for Longest Palindromic Substring

## 改进 ##

### DP的改进 ###

建立一张n\*n的表格，  
另i,j为下标，P(i,j)为true或者false，根据i和j之间是不是回文子串  
因为P(i,j)=P(i-1,j+1) && s\[i\]==s\[j\]，  
所以可不断扩充i和j之间的长度来建立这张表

### 巧妙的方法：从中心扩展 ###

这道题有一个更巧妙的方法，在 o ( n 2 ) o(n^2) o(n2) 的时间下进行，但是没有使用DP的思想.  
即，从回文串的特点出发：回文串从中间对称。  
那么对于一个长度为n的字符串，就有2n-1个中心，逐个从中心计算长度即可

public String longestPalindrome(String s) { 
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) { 
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) { 
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    private int expandAroundCenter(String s, int left, int right) { 
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { 
            L--;
            R++;
        }
        return R - L - 1;
    }

## Manacher’s Algorithm (O(n)) ##

码住，有时间再看

## 总结 ##

初看题目，如果需要不断移动 下标 i 和 j 来确定某个规则，即可建立一张n\*n的表的问题即可用dp做