5. Longest Palindromic Substring（求最长回文子字符串）

ゝ一世哀愁。 2022-06-09 12:17 170阅读 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"

**题目大意：**给定一个字符串，找到最长的回文子串。

**解法一：**

**解题思路：**回文字符串有两种情况：长度为奇数，或者长度为偶数。现在分别以这两种情况进行解题，两个int类型的指针left和right，分别向两侧延伸，以找到长度最大的回文子字符串。

**解题代码：（**44ms，beats 44.34%）

class Solution {
        public String longestPalindrome(String s) {
            if (s.length() <= 1) {
    			return s;
    		}
    		int left, right;
    		String res = s.substring(0, 1);
    		for (int i = 0; i < s.length(); i++) {
    			left = right = i;
    			while (left > -1 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    				left--;
    				right++;
    			}
    			if (right - left - 1 > res.length()) {
    				res = s.substring(left + 1, right);
    			}
    		}
    
    		for (int i = 0; i < s.length() - 1; i++) {
    			left = i;
    			right = i + 1;
    			while (left > -1 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    				left--;
    				right++;
    			}
    			if (right - left - 1 > res.length()) {
    				res = s.substring(left + 1, right);
    			}
    		}
    
    		return res;
        }
    }

**解法二：**

**解题思路：**动态规划

**解题代码：**（180ms，beats 1.67%）

class Solution {
        public String longestPalindrome(String s) {
            int sLen = s.length();
    		if (sLen <= 1) {
    			return s;
    		}
    		boolean[][] isPalindrome = new boolean[sLen][sLen];
    		// 初始化，i=j时只有一个字符，是回文字符串。i>j时是空串，也视为回文字符串。i<j时先默认初始化为false。
    		for (int i = 0; i < sLen; i++) {
    			for (int j = 0; j < sLen; j++) {
    				if (i < j) {
    					isPalindrome[i][j] = false;
    				} else {
    					isPalindrome[i][j] = true;
    				}
    			}
    		}
    		int left = 0, right = 0;
    		for (int step = 1; step < sLen; step++) {
    			for (int i = 0; i + step < sLen; i++) {
    				int j = i + step;
    				if (s.charAt(i) != s.charAt(j)) {
    					isPalindrome[i][j] = false;
    				} else {
    					isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
    					if (isPalindrome[i][j] == true) {
    						if (j - i > right - left) {
    							left = i;
    							right = j;
    						}
    					}
    				}
    
    			}
    		}
    		return s.substring(left, right + 1);
        }
    }