A fast java solution


  • 0
    S
        public int longestPalindromeSubseq(String s) {
            int n = s.length();
            if (n == 0)
                return 0;
            int[][] dp = new int[n][n];
            boolean[][] flag = new boolean[n][n];
            
            return memorySearch(dp, flag,0, n-1, s.toCharArray());
        }
        
        public int memorySearch(int[][] dp, boolean[][] flag, int l, int r, char[] str) {
            if (l > r)
                return 0;
            if (l == r)
                return 1;
            if (flag[l][r])
                return dp[l][r];
            int result = 0;
            if (str[l] == str[r]) {
                result = 2 + memorySearch(dp, flag, l+1,r-1,str);
            } else {
                result = Math.max(memorySearch(dp, flag, l+1,r,str),
                                    memorySearch(dp,flag,l,r-1,str));
            }
            flag[l][r] = true;
            dp[l][r] = result;
            return result;
        }
    }

Log in to reply
 

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