Java recursion with memoization


  • 0
    V
        HashMap<Integer, Integer> hm;
        public int longestPalindromeSubseq(String s) 
        {
            hm = new HashMap<Integer, Integer>();
            return dfs(s, 0 , s.length() - 1);
        }
        int dfs(String s, int st, int ed)
        {
            if(st == ed)
                return 1;
            if(st > ed || st >= s.length() || ed < 0)
                return 0;
            Integer k = st * 1000 + ed;
            int v = hm.getOrDefault(k, -1);
            if(v != -1)
                return v;
            int cnt = 0;
            if(s.charAt(st) == s.charAt(ed))
                cnt = 2 + dfs(s, st + 1, ed - 1);
            else
                cnt = Math.max(dfs(s, st + 1, ed), dfs(s, st, ed - 1));
            hm.put(k, cnt);
            return cnt;
        }

Log in to reply
 

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