Simple and easy to understand Java O(n^2) solution


  • 0
    M
    class Solution {
        public String longestPalindrome(String s) {
            int length = s.length();
            boolean[][] dp = new boolean[length][length];
            
            int start = 0;
            int end = 0;
            for (int len = 1; len <= length; len++) {
                for (int i = 0; i+len-1 < length; i++) {
                    int j = i+len-1;
                    if (s.charAt(i) != s.charAt(j)) {
                        dp[i][j] = false;
                    } else if (j-i < 2) {
                        dp[i][j] = true;
                    } else if (dp[i+1][j-1]) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = false;
                    }
                    if (dp[i][j] && j-i > end-start) {
                        start = i;
                        end = j;
                    }
                }
            }
            
            return s.substring(start, end+1);
        }
    }
    

Log in to reply
 

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