Java recursion + DP Top 75%


  • 0
    M

    The idea is to recur on n-1 to get the child, while caching solutions that have already being found on a list, in order to reduce by an order of O(n) the recursion time cost, at the expense of O(n) size

    public class Solution {
        
        public String countAndSay ( int n){
            return countAndSay(n, new ArrayList<String>(n));
        }
        public String countAndSay(int n, List<String> aux) {
            if (n==1) {
                aux.add(0,"1");
                return "1";
            }
            String s;
            if (aux.size() >= n-1)
                s = aux.get(n-2);
            else
                s = countAndSay(n-1, aux);
            StringBuilder sb = new StringBuilder();
            char prev=s.charAt(0);
            int cont=1;
            for (int i=1; i< s.length(); i++){
                if (s.charAt(i) == prev) cont++;
                else {
                     sb.append(cont);
                     sb.append(prev);
                     prev=s.charAt(i);
                     cont=1;
                }
            }
            sb.append(cont);
            sb.append(prev);
            aux.add(n-1, sb.toString());
            return aux.get(n-1);
        }
    }
    

Log in to reply
 

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