An easy way to understand this question


  • 0
    W

    If we reverse the input string first, eg. "acbac" to "cabca", considering the symmetric characteristic of palindrome,
    then this question will be simplified to "find the longest sub-sequence of these two strings"
    Below is a java solution:

    public int longestPalindromeSubseq(String s) {   
        if (s == null || s.length() == 0) {
            return 0;
        }
       
        char[] input = s.toCharArray();
        char[] reverse = new char[input.length];
        for (int i = 0; i < input.length; i++) {
            reverse[i] = input[input.length - 1 - i];
        }
        
        int[] result = new int[input.length + 1];
        for (int i = 1; i <= input.length; i++) {
            int[] pre = Arrays.copyOf(result, result.length);
            for (int j = 1; j <= input.length; j++) {
                result[j] = input[i - 1] == reverse[j - 1] ? pre[j - 1] + 1 : Math.max(result[j - 1], pre[j]);
            }
        }
        return result[input.length];
    }

Log in to reply
 

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