• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Dec 7th, 2018 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution
2. {
3.     HashMap<String, Integer> map = new HashMap<String, Integer>();
4.
5.     public int longestPalindromeSubseq(String s)
6.     {
7.         return compute(s, 0, s.length()-1);
8.     }
9.
10.     public int compute(String s, int low, int high)
11.     {
12.         if(low>high)    return 0;
13.         if(low==high)   return 1;
14.
15.         if(map.containsKey(s))
16.             return map.get(s);
17.
18.         if(s.charAt(low)==s.charAt(high))
19.         {
20.             int ans = compute(s, low+1, high-1);
21.             map.put(s.substring(low+1, high), ans);
22.             return 2+ans;
23.         }
24.         else
25.         {
26.             int ans1 = compute(s, low, high-1);
27.             int ans2 = compute(s, low+1, high);
28.
29.             map.put(s.substring(low, high-1), ans1);
30.             map.put(s.substring(low+1, high), ans2);
31.
32.             return Math.max(ans1, ans2);
33.         }
34.     }
35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top