Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution
- {
- HashMap<String, Integer> map = new HashMap<String, Integer>();
- public int longestPalindromeSubseq(String s)
- {
- return compute(s, 0, s.length()-1);
- }
- public int compute(String s, int low, int high)
- {
- if(low>high) return 0;
- if(low==high) return 1;
- if(map.containsKey(s))
- return map.get(s);
- if(s.charAt(low)==s.charAt(high))
- {
- int ans = compute(s, low+1, high-1);
- map.put(s.substring(low+1, high), ans);
- return 2+ans;
- }
- else
- {
- int ans1 = compute(s, low, high-1);
- int ans2 = compute(s, low+1, high);
- map.put(s.substring(low, high-1), ans1);
- map.put(s.substring(low+1, high), ans2);
- return Math.max(ans1, ans2);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement