LeetCode - Medium - 5. Longest Palindromic Substring

今天药忘吃喽~ 2022-12-31 12:28 126阅读 0赞

## Topic ##

*  String
 *  Dynamic Programming

## Description ##

[https://leetcode.com/problems/longest-palindromic-substring/][https_leetcode.com_problems_longest-palindromic-substring]

Given a string `s`, return the longest palindromic substring in `s`.

**Example 1**:

Input: s = "babad"
    Output: "bab"
    Note: "aba" is also a valid answer.

**Example 2**:

Input: s = "cbbd"
    Output: "bb"

**Example 3**:

Input: s = "a"
    Output: "a"

**Example 4**:

Input: s = "ac"
    Output: "a"

**Constraints**:

*  1 <= s.length <= 1000
 *  `s` consist of only digits and English letters (lower-case and/or upper-case),

## Analysis ##

方法一：以字符为中心向其两侧扩展探测是否回文。

--------------------

方法二：动态规划。

`dp(i, j)` represents whether `s(i ... j)` can form a palindromic substring, `dp(i, j)` is true when `s(i)` equals to `s(j)` and `s(i+1 ... j-1)` is a palindromic substring.

When we found a palindrome, check if it’s the longest one. Time complexity O(n^2).

以 s = “babad” 为例，dp数组如下：

j 0 1 2 3 4
    i   b a b a d
    0 b t   t    
    1 a   t   t  
    2 b     t    
    3 a       t  
    4 d         t

*  **`j` must be greater than or equal `i` at all times. Why**? `i` is the start index of the substring, `j` is the end index of the substring. It makes no sense for `i` to be greater than `j`. If you visualize the dp 2d array, think of a diagonal that cuts from top left to bottom right. We are only filling the top right half of dp.
 *  **Why are we counting down for `i`, but counting up for `j`**? Each sub-problem `dp[i][j]` depends on `dp[i+1][j-1]` (`dp[i+1][j-1]` must be true and `s.charAt(i)` must equal `s.charAt(j)` for `dp[i][j]` to be true).
 *  **How to understand `dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);`**?
    
     *  `j-i == 0`, only a character is a palindrome.
     *  `j-i == 1` and `s.charAt(i) == s.charAt(j)`, `s[i:j]` is a palindrome.(like “aa”，“bb”)
     *  `j-i == 2` and `s.charAt(i) == s.charAt(j)`, no matter what between `i` and `j`, `s[i:j]` is a palindrome.(like “aba”, “aza”)

**动态规划解决问题的套路**：

*  需要用动态规划解决问题的味道
    
     *  “最值”味道。（本题的 **the longest** palindromic substring in s）
 *  用动态规划解决问题的4步曲
    
    1.  确定状态。（`dp(i, j)` represents whether `s(i ... j)` can form a palindromic substring）
    2.  求得方程。（`dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);`）
    3.  设初置界。（0 <= i <= j < s.length）
    4.  确序而答。（由方程可知，`dp[i][j]`是依赖`dp[i + 1][j - 1]`的，因此，i从大到小，j则从小到大）

## Submission ##

public class LongestPalindromicSubstring { 
    
    	// 方法一：以中心字符扩展探测回文
    	public String longestPalindrome1(String s) { 
    		int maxLen = 0, startIndex = 0;
    
    		for (int i = 0; i < s.length(); i++) { 
    			int len1 = extend(s, i, i);
    			int len2 = extend(s, i, i + 1);
    			int tempMax = Math.max(len1, len2);
    
    			if (tempMax > maxLen) { 
    				maxLen = tempMax;
    				startIndex = len1 > len2 ? i - len1 / 2 : i - len2 / 2 + 1;
    			}
    		}
    
    		return s.substring(startIndex, startIndex + maxLen);
    	}
    
    	private int extend(String s, int i, int j) { 
    		for (; i > -1 && j < s.length(); i--, j++) { 
    			if (s.charAt(i) != s.charAt(j))
    				break;
    		}
    		return j - i - 1;
    	}
    
    	// 方法二：使用动态规划算法
    	public String longestPalindrome2(String s) { 
    		int sLength = s.length();
    		String res = null;
    
    		boolean[][] dp = new boolean[sLength][sLength];
    
    		//startIndex相当于i，endIndex相当于j，改名方便理解。
    		for (int startIndex = sLength - 1; startIndex >= 0; startIndex--) { 
    			for (int endIndex = startIndex; endIndex < sLength; endIndex++) { 
    				dp[startIndex][endIndex] = s.charAt(startIndex) == s.charAt(endIndex) // 
    						&& (endIndex - startIndex < 3 || dp[startIndex + 1][endIndex - 1]);
    
    				if (dp[startIndex][endIndex] && (res == null || endIndex - startIndex + 1 > res.length())) { 
    					res = s.substring(startIndex, endIndex + 1);
    				}
    			}
    		}
    
    		return res;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import static org.hamcrest.Matchers.*;
    
    import org.junit.Test;
    
    public class LongestPalindromicSubstringTest { 
    
    	@Test
    	public void test() { 
    		LongestPalindromicSubstring obj = new LongestPalindromicSubstring();
    
    		assertEquals("bb", obj.longestPalindrome1("cbbd"));
    		assertEquals("a", obj.longestPalindrome1("a"));
    		assertThat(obj.longestPalindrome1("ac"), anyOf(is("a"), is("c")));
    		assertThat(obj.longestPalindrome1("babad"), anyOf(is("bab"), is("aba")));
    		
    		assertEquals("bb", obj.longestPalindrome2("cbbd"));
    		assertEquals("a", obj.longestPalindrome2("a"));
    		assertThat(obj.longestPalindrome2("ac"), anyOf(is("a"), is("c")));
    		assertThat(obj.longestPalindrome2("babad"), anyOf(is("bab"), is("aba")));
    	}
    }

[https_leetcode.com_problems_longest-palindromic-substring]: https://leetcode.com/problems/longest-palindromic-substring/