Show an Answer in Java


  • 46
    R

    I found nobody answered this question in Java. Actually I got some trouble even this question is not so hard.

    Maybe many other people had some trouble too. So I put my answer here.

    public class Solution {
        public String countAndSay(int n) {
    	    	StringBuilder curr=new StringBuilder("1");
    	    	StringBuilder prev;
    	    	int count;
    	    	char say;
    	        for (int i=1;i<n;i++){
    	        	prev=curr;
    	 	        curr=new StringBuilder();       
    	 	        count=1;
    	 	        say=prev.charAt(0);
    	 	        
    	 	        for (int j=1,len=prev.length();j<len;j++){
    	 	        	if (prev.charAt(j)!=say){
    	 	        		curr.append(count).append(say);
    	 	        		count=1;
    	 	        		say=prev.charAt(j);
    	 	        	}
    	 	        	else count++;
    	 	        }
    	 	        curr.append(count).append(say);
    	        }	       	        
    	        return curr.toString();
            
        }
    }
    

    @code StringBuilder.append() is the default way to append one string to another. While I have tried String.cancate(),which is not working properly.

    Any comment is welcomed.


  • 3
    L
    //This is my answer , it's Accept. I hope it can help you:
    public String countAndSay(int n) {
    	if(n<=0) {
    		return "";
    	}
    	
    	String nowStr="1";
    	for(int current=1; current<n; current++) {
    		nowStr = getSay(nowStr);
    	}
        return nowStr;
    }
    
    String getSay(String pre) {
    	int count =0;
    	StringBuilder reStr = new StringBuilder("");
    	for(int i = 0; i<pre.length(); i++){
    		count ++;
    		if ((i+1 < pre.length()) && (pre.charAt(i) != pre.charAt(i + 1))) {
    			reStr = reStr.append(count).append(pre.charAt(i));
    			count = 0;
    		}
    		else if ((i+1 == pre.length())) {
    			reStr = reStr.append(count).append(pre.charAt(i));
    		}	
    	}
    	return reStr.toString();
    }
    

  • 2
    Z

    You don't need to do new String(result). String is immutable in Java.
    You can concatenate strings (or any other type to string) in java using "+" but in that case you rely on aggressiveness JIT optimizer - whether it will use StringBuilder or will create new String after every "+".

    Te same idea but it is recursive:

    public class Solution {
        public String countAndSay(int n) {
            if(n == 1)
                return "1";
    
            String prev = countAndSay(n - 1);
    
            StringBuilder sb = new StringBuilder();
            int count = 1;
            char prevNum = prev.charAt(0);
            for(int i = 1; i < prev.length(); ++i) {
                char curNum = prev.charAt(i);
                if(curNum == prevNum) {
                    ++count;
                }
                else {
                    sb.append(count);
                    sb.append(prevNum);
                    count = 1;
                }
                prevNum = curNum;
            }
            sb.append(count);
            sb.append(prevNum);
    
            return sb.toString();
        }
    }

  • 10
    Z

    I rewrote your solution using "+" and it works. The solution is better than mine - it wouldn't cause StackOverflowException.

    public class Solution {
        public String countAndSay(int n) {
            String result = "1";
            for (int outer = 1; outer < n; outer++) {
                String previous = result;
                result = "";
                int count = 1;
                char say = previous.charAt(0);
    
                for (int i = 1; i < previous.length(); i++) {
                    if (previous.charAt(i) != say) {
                        result = result + count + say;
                        count = 1;
                        say = previous.charAt(i);
                    } else count++;
                }
                result = result + count + say;
            }
            return result;
        }
    }

  • 0
    R

    I have made some change to my original solution. Take a look.


  • 0
    C

    Thanks for your sharing!


  • 0
    H

    In my first impressions, i choose BigInteger, then, take the remainder. 860ms while n=30.


  • 0
    E

    Here is a recursive way, which is not as efficient though:

    public String countAndSay(int n) {
        if(n==1) return "1";
        
        String res = "1";
        for(int i=2; i<=n; i++) {
            res = helper(res);
        }
        return res;
    }
    
    public String helper(String str) {
        int count = 1;
        String res = "";
        
        for(int i=1; i<str.length(); i++) {
            if(str.charAt(i) == str.charAt(i-1) )
                count++;
            else {
                res += ((Integer)count).toString() + str.charAt(i-1);
                count = 1;
            }
        }
        res += count + str.substring(str.length()-1, str.length());
        return res;
    }

  • 5
    E

    If we want to be short. Let's be as short as possible ;-)

    public class Solution {
        public String countAndSay(int n) {
            String s = "1";
            for (int i = 1; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 1, count = 1; j <= s.length(); j++) {
                    if (j == s.length() || s.charAt(j - 1) != s.charAt(j)) {
                        sb.append(count);
                        sb.append(s.charAt(j - 1));
                        count = 1;
                    } else {
                        count++;
                    }
                }
                s = sb.toString();
            }
            return s;
        }
    }

  • 3
    C

    I think you don't need to declare the 'prev', 'count' before go into the loop. And also I think 'say' is not necessary. Here is my solution:

        StringBuffer sb = new StringBuffer("1");
        for(int i = 1; i < n; i++) {
            int count = 1;
            StringBuffer temp = new StringBuffer();
            int len = sb.length();
            for(int j = 1; j < len; j++) {
                if(sb.charAt(j) != sb.charAt(j - 1)) {
                    temp.append(count);
                    temp.append(sb.charAt(j - 1));
                    count = 1;
                }
                else {
                    count++;
                }
            }
            temp.append(count);
            temp.append(sb.charAt(len - 1));
            sb = temp;
        }
        return sb.toString();

  • 0
    A

    @ElementNotFoundException This is not a recursive approach. You are running the function in series one after the other using for loop.


  • 0
    W

    I am confused about the solution code

    in second last setence, why need another curr.append(count).append(say); outside for loop?

    I thought the curr should be complete after the second inner for loop. Can anyone explain?
    Thx!


  • 0
    C
    public class Solution {
        public String countAndSay(int n) {
            if (n == 0) {
                return "";
            }
            
            String s = "1";
            
            for (int i = 1; i < n; i++) {
                s = say(s);
            }
            
            return s;
        }
        
        private String say(String s) {
            if (s.length() < 1) {
                return "";
            }
            
            if (s.length() == 1) {
                return "1" + s;
            }
            
            int count = 1;
            StringBuilder sb = new StringBuilder();
            
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == s.charAt(i - 1)) {
                    count++;
                }
                else {
                    sb.append(count);
                    sb.append(s.charAt(i - 1));
                    count = 1;
                }
            }
            
            sb.append(count);
            sb.append(s.charAt(s.length() - 1));
            
            return sb.toString();
        }
    }
    
    

  • 0
    This post is deleted!

  • 0

    @zerobased Thanks for sharing, great one! But I just have some problem when I wrote result = result + count + say as result += count + say. And got different answer! Could you or anyone please tell me why?? Thanks a lot!


  • 0
    public class Solution {
        public String countAndSay(int n) {
            if (n <= 0) {
                return "";
            }
            String ans = "1";
            while (n > 1) {
                String temp = "";
                char[] array = ans.toCharArray();
                for (int i = 0; i < array.length; i++) {
                    int count = 1;
                    while (i + 1 < array.length && array[i] == array[i+1]) {
                        i++;
                        count++;
                    }
                    temp = temp + count + array[i];
                }
                ans = temp;
                n--;
            }
            return ans;
        }
    }
    

    Seems like string can't support +=. I tried temp +=, but it gave wrong answers. I guess maybe only int support += and string can only be assigned with a complete value. Anyone knows?


  • 0
    A

    What is the time and space complexity for your solution ?


  • 1

    @EdickCoding Here is mine. :)

        public String countAndSay(int n) {
            String s = "1";
            while (n-- > 1) { /* invariant: s is nth */
                StringBuilder next = new StringBuilder(); /* invariant: contain cnt-say before cur */
                for (int i = 1, cnt = 1; i <= s.length(); i++, cnt++) {
                    if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) {
                        next.append(cnt).append(s.charAt(i - 1));
                        cnt = 0;
                    }
                }
                s = next.toString();
            }
            return s;
        }
    

    ps: There are some connection between this problem and Summary Range, Encode String or other similar problems. It's seems like very necessary to get familiar with the way of this kind of iteration.

        // 228 Summary Ranges 24.1% Medium
        public List<String> summaryRanges(int[] nums) {
            List<String> ret = new ArrayList<>();
            int n = nums.length;
            for (int i = 1, j = 0; i <= n; i++) {
                if (i == n || nums[i - 1] != nums[i] - 1) {
                    ret.add(j == i - 1 ? nums[j] + "" : nums[j] + "->" + nums[i - 1]);
                    j = i;
                }
            }
            return ret;
        }
    
        // Encode string from "aaabccccc" -> "3ab5c"
        public String encode(String word) {
            StringBuilder enc = new StringBuilder();
            int n = word.length();
            for (int i = 1, cnt = 1; i <= n; i++, cnt++) {
                if (i == n || word.charAt(i - 1) != word.charAt(i)) {
                    if (cnt > 1) {
                        enc.append(cnt);
                    }
                    enc.append(word.charAt(i - 1));
                    cnt = 0;
                }
            }
            return enc.length() < word.length() ? enc.toString() : word;
        }
    

  • 1

    It may be more natural for index to start from 0

    for(int j=0,count=1;j<s.length();j++){
               if(j==s.length()-1||s.charAt(j)!=s.charAt(j+1)){
                    sb.append(count).append(s.charAt(j));
    

    Also wonder the time complexity of this approach. Have seen some statements like O(n^2), but it seems that the growing of string s is not only linear, so I doubt O(n^2) is not sufficient, and may require O(2^n). And the space complexity would also be O(2^n) as we need to store the generated string.


  • 0
    G
    public class Solution {
        public String countAndSay(int n) {
            String str = "1";
            while (--n > 0) {
                str = countAndSay(str);
            }
            return str;
        }
        private String countAndSay(String s) {
            StringBuilder sb = new StringBuilder();
            int pos = 0;
            while (pos < s.length()) {
                int count = 1;
                while (pos < s.length() - 1 && s.charAt(pos) == s.charAt(pos + 1)) {
                    count++;
                    pos++;
                }
                sb.append(count + "" + s.charAt(pos));
                pos++;
            }
            return sb.toString();
        }
    }

Log in to reply
 

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