5. Longest Palindromic Substring

• 5. Longest Palindromic Substring
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Intuition

这题目除了传统方法，可以继续用dp来骚

subtring [i, j] 可以由 substring [i + 1, j - 1] 得出 如果 [i + 1, j - 1] is a palindrome, and s[i] == s[j] 显然也是

Pitfall

Solution

  public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
      return "";
    }
    final boolean[][] dp = new boolean[s.length()][s.length()];
    String res = "";

    for (int i = s.length() - 1; i >= 0; i--) {
      for (int j = i; j < s.length(); j++) {
        dp[i][j] = (2 >= j - i || dp[i + 1][j - 1]) && (s.charAt(i) == s.charAt(j));

        if (dp[i][j] && (j - i + 1) > res.length()) {
          res = s.substring(i, j + 1);
        }
      }
    }
    return res;
  }

Solution