[LeetCode 5] Longest Palindromic Substring

Question

link

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Stats

Frequency	2
Diffficulty	4
Adjusted Difficulty	4
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are 2 solutions. One is DP which is O(N^2) time and O(N^2) space. Another is “Search around corner”, which uses less space.

Solution

DP solution is straight-forward. Use 2D array to check palindrome intervals and make it as either true or false. Meanwhile, update longest.

O(N^2) time and O(N^2) space

Search around corner is basically iterate through the entire string and assume each char (or char pair) as center of the palindrome. The code isn’t difficult once you come up with the idea.

For more, read this post

O(N^2) time and O(1) space

My code

DP solution

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String longest = "";
        int len = s.length();
        // dp[i][j] means substring of s from i to j is palindrome
        boolean[][] dp = new boolean[len][len];
        // why i decrease from (len-1) to 0, but j increase from i to (len-1)?
        // think about it!
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (i + 1 == j) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    // important to note: dp[i+1][j-1]
                    // i depends on (i+1), so i from large to small
                    // j is just the opposite, small to large
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
                if (dp[i][j] && j + 1 - i > longest.length()) {
                    longest = s.substring(i, j + 1);
                }
            }
        }
        return longest;
    }
}

Search around corner

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1)
            return s;
        String largest = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String first = this.searchAroundCenter(s, i, i);
            String second = this.searchAroundCenter(s, i, i + 1);
            if (first.length() < second.length())
                first = second;
            if (largest.length() < first.length())
                largest = first;
        }
        return largest;
    }

    private String searchAroundCenter(String s, int a, int b) {
        if (a < 0 || b > s.length() - 1)
            return "";
        while (s.charAt(a) == s.charAt(b)) {
            a--;
            b++;
            if (a < 0 || b > s.length() - 1)
                return s.substring(a + 1, b);
        }
        return s.substring(a + 1, b);
    }
}