Why the same method has two different running time?


  • 0
    A

    Why these two solutions have different running time?

    my solution 7ms:

    public class Solution {
        public String countAndSay(int n) {
            if (n == 1) return "1";
            if (n == 2) return "11";
            String cur_s = "11";
            for (int i = 2; i < n; i++) {
                StringBuffer new_s = new StringBuffer();
                char[] cur_c = cur_s.toCharArray();
                int cnt = 1;
                for (int j = 0; j < cur_c.length-1; j++) {
                    if (cur_c[j] == cur_c[j+1]) cnt ++;
                    else {
                        new_s.append(String.valueOf(cnt) + cur_c[j]);
                        cnt = 1;
                    }
                }
                if (cur_c[cur_c.length-1] == cur_c[cur_c.length-2]) new_s.append(String.valueOf(cnt) + cur_c[cur_c.length-1]);
                else {
                    new_s.append(String.valueOf(1) + cur_c[cur_c.length-1]);
                }
                cur_s = new_s.toString();
            }
            return cur_s;
        }
    
    }
    

    While the other one from charliewang92's solution only takes for 2ms:

    public class Solution {
    public String countAndSay(int n) {
        String start = "1";
        if (n == 1) {
            return start; 
        }
        int counter = 1;
        while(counter < n) {
            start = helper(start); 
            counter++;
        }
    
        return start; 
    }
    
    public String helper(String s) {
        char curr =  s.charAt(0);
        int counter = 0;
        StringBuffer sb = new StringBuffer(); 
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i) == curr) {
                counter++; 
            } else {
                sb.append(counter);
                sb.append(s.charAt(i-1));
                counter = 1; 
                curr = s.charAt(i);
            }
    
        }
        sb.append(counter);
        sb.append(curr);
        return sb.toString(); 
    } 
    

    I don't see significant difference with these two solutions, any ideas?


Log in to reply
 

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