leetcode-lintcode/005_longest_palindromic_substring.java at master · lt616/leetcode-lintcode · 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/* Solution 01: looping midpoint */

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        String maxSubString = "";
        for (int i = 0; i < s.length(); i++) {
            String str= findLongestPalindrome(s, i, i + 1);
            if (str != null && str.length() > maxSubString.length()) {
                maxSubString = str;
            }

            str = findLongestPalindrome(s, i - 1, i + 1);
            if (str != null && str.length() > maxSubString.length()) {
                maxSubString = str;
            }
        }

        return maxSubString;
    }

    private String findLongestPalindrome(String s, int start, int end) {
        /* even length */
        while (start >= 0 && end < s.length()) {
            if (s.charAt(start) != s.charAt(end)) {
                break;
            }
            start --;
            end ++;
        }
        start ++;
        end --;
        return s.substring(start, end + 1);
    }
}


/* Solution 02: Dynamic DP */
class Solution {
    boolean[][] visited;
    boolean[][] memo;

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        visited = new boolean[s.length()][s.length()];
        memo = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length();j ++) {
                visited[i][j] = false;
                memo[i][j] = false;
            }
        }

        String maxSubString = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            for (int j = i - 1; j >= 0; j --) {
                if (isPalindrome(s, j, i) && (i - j + 1) > maxSubString.length()) {
                    maxSubString = s.substring(j, i + 1);
                }
            }
        }
        return maxSubString;
    }

    private boolean isPalindrome(String s, int start, int end) {
        if (start < 0 || start >= s.length() || end < 0 || end >= s.length() || start > end) {
            return true;
        }

        if (visited[start][end]) {
            return memo[start][end];
        }

        visited[start][end] = true;
        if (start == end) {
            memo[start][end] = true;
            return true;
        }

        if (s.charAt(start) == s.charAt(end)) {
            memo[start][end] = isPalindrome(s, start + 1, end - 1);
            return memo[start][end];
        }

        memo[start][end] = false;
        return memo[start][end];
    }
}