DP Java solution


  • 0
    A

    Uses dynamic programming

    public class Solution {
        public String countAndSay(int n) {
            if(n == 1){return "1";} if(n == 2){ return "11";} if (n== 3){return "21";}
            String[] arr = new String[n];
            arr[0] = "1"; arr[1] = "11"; arr[2] = "21";
            for(int i = 3; i < n; i++){ 
                String prev = arr[i - 1];
                int count_char = 1;
                char c = prev.charAt(0); 
                 StringBuilder sb = new StringBuilder();
                for(int k = 1; k < prev.length(); k++){
                     if(prev.charAt(k) != c){
                         sb.append(String.valueOf(count_char)).append(String.valueOf(c));
                         c = prev.charAt(k);
                         count_char = 1;
                     } else{
                         count_char++;
                     }
                }
                sb.append(String.valueOf(count_char)).append(String.valueOf(c));
                arr[i] = sb.toString();
            }
        return arr[n - 1];
        }
    }
    

Log in to reply
 

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