My 380ms java solution with DP


  • 1
    B
    public class Solution {
        public String longestPalindrome(String s) {
            int[] farest = new int[s.length()];
            for (int i = 0; i < farest.length; i++) {
                farest[i] = i;
            }
            for (int i = 1; i < s.length(); i++) {
                int first = farest[i - 1] - 1;
                if (first >= 0 && s.charAt(i) == s.charAt(first)) {
                    farest[i] = first;
                } else {
                    for (int j = first + 1; j <= i; j++) {
                        if (isPalindrome(s.substring(j, i + 1))) {
                            farest[i] = j;
                            break;
                        }
                    }
                }
            }
            int maxDiff = 0;
            int pos = 0;
            for (int i = 0; i < s.length(); i++) {
                if (i - farest[i] > maxDiff) {
                    maxDiff = i - farest[i];
                    pos = i;
                }
            }
            return s.substring(farest[pos], pos + 1);
        }
        public boolean isPalindrome(String s) {
            char[] cc = s.toCharArray();
            int start = 0;
            int end = s.length() - 1;
            while (start < end) {
                if (cc[start] != cc[end]) {
                    return false;
                }
                start++;
                end--;
            }
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.