Share accepted Java solution with memoization


  • 0
    I
    package com.leetcode.oj;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class CountAndSay {
        private final List<String> memo;
    
        public CountAndSay() {
            memo = new ArrayList<>();
            memo.add("");
            memo.add("1");
        }
    
        public String countAndSay(int n) {
            if (memo.size() > n) {
                return memo.get(n);
            }
            while (memo.size() <= n+1) {
                String lastSay = memo.get(memo.size() - 1);
                String nextSay = nextSay(lastSay);
                memo.add(nextSay);
            }
            return memo.get(n);
        }
    
        String nextSay(String lastSay) {
            char elem = lastSay.charAt(0);
            int count = 1;
            StringBuilder ret = new StringBuilder();
            for (int i = 1; i < lastSay.length(); ++i) {
                if (lastSay.charAt(i) == elem) {
                    ++count;
                } else {
                    ret.append(count);
                    ret.append(elem);
                    elem = lastSay.charAt(i);
                    count = 1;
                }
            }
            ret.append(count);
            ret.append(elem);
            return ret.toString();
        }
    }

Log in to reply
 

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