Java Dynamic Programming Solution - 8ms Worst case, but getting TLE


  • 0
    E

    My idea is s[n] will know the longest palindrome in 0...n substring. When we move to i, it must create a larger palindrome than s[i -1] knows of for it to be considered. To check that we start looking for ith character from start. When we find one (lets say at m index), we check if m...i is a palindrome. If not, we keep looking til the length becomes smaller than what s[i - 1] knows of. If none found, then we carry forward the same palindrome that s[i - 1] to s[i];

        public String longestPalindrome(String input) {
            if ((input == null) || (input.length() <= 1)) {
                return input;
            }
    
            String[] s = new String[input.length()];
            int longestPalindromeLength;
            s[0] = input.substring(0, 1);
            //System.out.println("s[0]: " + s[0]);
            int j;
            for (int i = 1; i < input.length(); i++) {
                longestPalindromeLength = s[i - 1].length();
                j = 0;
                while (j <= i - longestPalindromeLength) {
                    if (input.charAt(i) == input.charAt(j)) {
                        //System.out.println("checking palindrome from " + j + " - " + (i + 1) + ": " + input.substring(j, i + 1));
                        if (isPalindrome(input.substring(j, i + 1))) {
                            //System.out.println("found palindrome from " + j + " - " + (i + 1) + ": " + input.substring(j, i + 1));
                            s[i] = input.substring(j, i + 1);
                            break;
                        }
                    }
    
                    j++;
                }
    
                if (s[i] == null) {
                    s[i] = s[i - 1];
                }
    
                //System.out.println("s[" + i + "]: " + s[i]);
            }
    
            return s[input.length() - 1];
        }
    
        private boolean isPalindrome(String input) {
            if ((input == null) || (input.length() <= 1)) {
                return true;
            }
    
            int size = input.length();
            for (int i = 0; i <= size / 2; i++) {
                if (input.charAt(i) != input.charAt(size - i - 1)) {
                    return false;
                }
            }
    
            return true;
        }

Log in to reply
 

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