Iterative and recursive Java solution


  • 0
    Y
    public class Solution {
        /** Recursion */
        public String countAndSay(int n) {
            if (n <= 1) return "1";
            StringBuilder sb = new StringBuilder();
            StringBuilder tmp = new StringBuilder(countAndSay(n - 1));
            int index = 0;
            int count = 1;
            while (index < tmp.length()) {
                char curr = tmp.charAt(index++);
                while (index < tmp.length() && tmp.charAt(index) == curr) {
                    ++count;
                    ++index;
                }
                sb.append(String.valueOf(count) + String.valueOf(curr));
                count = 1;
            }
            return sb.toString();
        }
        
        
        /**
         * Iteration
         * Append a "1" to the stringbuilder as the initial case.
         * Use a tmp stringbuilder to store the temporary result of each for loop. 
         * Traverse the sb builder for each i, and cound for the same and consecutive numbers. 
         * Then append corresponding cound and say number into tmp string until reaching the end of tmp.
         * Set sb to tmp. 
         * O(n ^ n) time since we have to calculate every result from 2 to n, O(n) space */
        public String countAndSay(int n) {
            StringBuilder sb = new StringBuilder();
            sb.append("1");
            if (n <= 1) return sb.toString();
            for (int i = 2; i <= n; i++) {
                StringBuilder tmp = new StringBuilder();
                int count = 1;
                int index = 0;
                while (index < sb.length()) {
                    char curr = sb.charAt(index++);
                    while (index < sb.length() && sb.charAt(index) == curr) {
                        ++count;
                        ++index;
                    }
                    tmp.append(String.valueOf(count) + String.valueOf(curr));
                    count = 1;
                }
                sb = tmp;
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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