coding-problems/Leetcode/LongestPalindromicSubstring.java at master · roboGOD/coding-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class LongestPalindromicSubstring {

}

class Solution {

  //////////////////////////////////////////////////////
  // DP Solution
  public String longestPalindrome(String s) {
      int maxLen = 0;
      String result = "";
      int ri=-1, rj=-1;
      int n = s.length();
      boolean[][] dp = new boolean[n][n];

      for(int k=0; k<n; k++) {
          for(int i=0; k+i<n; i++) {
              int j = i+k;
              if(j-i == 0) {
                  dp[i][j] = true;
              } else if(j-i == 1) {
                  dp[i][j] = s.charAt(i) == s.charAt(j);
              } else {
                  dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
              }

              // System.out.println(i + " " + j + " " + dp[i][j]);

              if(dp[i][j] && j-i+1 >= maxLen) {
                  maxLen = j-i+1;
                  ri = i;
                  rj = j;
              }
          }
      }

      if(ri != -1 && rj != -1) {
          result = s.substring(ri, rj+1);
      }

      return result;
  }
}