Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 7th, 2018 50 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  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. OK, I Understand
 
Top