LeetCode 5. Longest Palindromic Substring

以你之姓@ 2021-06-24 15:57 325阅读 0赞

## **一、试题** ##

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.  
Example:

Input: “cbbd”

Output: “bb”

## **二、代码** ##

传统方法，逐渐遍历查找。

class Solution {
    public:
        string longestPalindrome(string s) {
    	pair<int,int> pos;
    	int max=0;
    	for(int i=0; i<s.size(); i++){
    		int st=i,en=i;
    		while(s[st]==s[en] && st>=0 && en<s.size()){
    			st--,en++;
    		}
    		if(en-st-1>max){
    			max = en-st-1;
    			pos = make_pair(st+1,en);
    		}
    		if(i+1<s.size() && s[i]==s[i+1]){
    			int st=i,en=i+1;
    			while(s[st]==s[en] && st>=0 && en<s.size()){
    				st--,en++;
    			}
    			if(en-st-1>max){
    				max = en-st-1;
    				pos = make_pair(st+1,en);
    			}			
    		}
    	}
    	cout<<pos.first<<pos.second;
    
    	return s.substr(pos.first,pos.second-pos.first);  
        }
    };

// 对字符串每个位置展开查找
    class Solution {
        public String longestPalindrome(String s) {
            if(s==null || s.length()==0) 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){
            while( left>=0 && right<s.length() && s.charAt(left)==s.charAt(right) ){
                left--;
                right++;
            }
            return right-left-1;
        }
    }

dp查找
    class Solution {
        public String longestPalindrome(String s) {
            if(s == null || s.length() == 0) return "";
            int len = s.length();
            int start = 0;
            int end = 0;
            boolean[][] dp = new boolean[len][len];
            
            for(int i = 0; i < len; i++){
                dp[i][i] = true;
                if(i < len - 1 && s.charAt(i) == s.charAt(i+1)){
                    dp[i][i+1] = true;
                    if(end - start < 1){
                        start = i;
                        end = i + 1;
                    }
                }
            }
            
            
            for(int i = 2; i < len; i++){
                for(int j = 0; j < len - i; j++){
                    dp[j][i+j] = (s.charAt(j) == s.charAt(i+j) && dp[j+1][i+j-1]);
                    if(dp[j][i+j] && end - start < i){
                        start = j;
                        end = i + j;
                    }
                }
            }
            
            
            return s.substring(start, end+1);
        }
    }