LeetCode - Medium - 5. Longest Palindromic Substring-蒲公英云

Topic

String
Dynamic Programming

Description

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")));
    }
}