Java Solution with BFS idea


  • 0
    J

    I perceive the problem as bfs on string. Each time you only need to cache the sequence from n - 1 level and construct new one based on that.

    public class Solution {
        public String countAndSay(int n) {
            if (n < 1) throw new IllegalArgumentException("Your input is invalid");
            Queue<Integer> q = new LinkedList<>();
            q.offer(1);
            for (int i = 1; i < n; i++) {
                int size = q.size();
                int count = 1;
                while (size > 0) {
                    int num = q.poll();
                    size--;
                    while (size != 0 && q.peek() == num) {
                        count++; q.poll(); size--;
                    }
                    q.offer(count);
                    q.offer(num);
                    count = 1;
                }
            }
            StringBuilder sb = new StringBuilder();
            while (!q.isEmpty()) sb.append(q.poll());
            return sb.toString();
        }
    }
    

Log in to reply
 

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