# Untitled

Aug 30th, 2020
1,158
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. public class Solution {
2.     /**
3.      * @param s: input string
4.      * @return: a string as the longest palindromic substring
5.      *
6.      * Solution: view this as Dynamic Programming
7.      * Solution: O(n^2)
8.      *
9.      */
10.     public String longestPalindrome(String s) {
11.         // check sanity first
12.         if (s == null || s.isEmpty()) {
13.             return "";
14.         }
15.
16.         // initialize
17.         String result = "";
18.         String possibleResult = "";
19.         int len = s.length();
20.         boolean isP[][] = new boolean[len][len]; // Java all initialized to false by default
21.
22.         // main code
23.         // odd base case (len == 1): isP[i][i+2] = isP[i+1][i+1] && ( s.charAt(i) == s.charAt(i+2) )
24.         for (int i = 0; i < len; i++) {
25.             int left = i;
26.             int right = i;
27.             isP[left][right] = true;
28.
29.             // update result
30.             if (isP[left][right]) {
31.                 result = giveFinalResult(result, s, left, right);
32.             }
33.         }
34.         // even base case (len == 2): isP[i][i+3] = isP[i+1][i+2] && ( s.charAt(i) == s.charAt(i+3) )
35.         for (int i = 1; i < len; i++) {
36.             int left = i-1;
37.             int right = i;
38.             if (s.charAt(left) == s.charAt(right)) {
39.                 isP[left][right] = true;
40.             }
41.
42.             // update result
43.             if (isP[left][right]) {
44.                 result = giveFinalResult(result, s, left, right);
45.             }
46.         }
47.
48.         // go - check & build at the same time from small to big
49.         for (int nowLen = 3; nowLen <= len; nowLen++) {
50.             int left = 0;
51.             int right = left + (nowLen - 1); // convert length to index concept
52.             while (true) {
53.                 if (right >= len) break;
54.
55.                 isP[left][right] = isP[left+1][right-1] && (s.charAt(left) == s.charAt(right)); // DP
56.
57.                 // update result
58.                 if (isP[left][right]) {
59.                     result = giveFinalResult(result, s, left, right);
60.                 }
61.
62.                 left++;
63.                 right++;
64.             }
65.         }
66.
67.         // get result
68.         return result;
69.     }
70.
71.
72.     private String giveFinalResult(String nowResult, String s, int left, int right) {
73.         String result = nowResult;
74.         String possibleResult = s.substring(left, right+1);
75.         if (possibleResult.length() > result.length()) {
76.             result = possibleResult;
77.         }
78.         return result;
79.     }
80.
81.
82. }
RAW Paste Data