A WOW difference in runtime: String and StringBuilder (Java). Can anybody explain me why?


  • 0
    M

    I was highly disappointed with runtime results of my first submission and tried to optimize. To my greatest surprise, I got ninefold (!!!) decrease in runtime by just using StringBuilder instead of String, with no changes in algorythm. Can anybody explain me why?????

    Please find below some stats and both my solutions:
    String version - avg runtime 36 ms, beating 9% of submissions;
    StringBuilder version - avg runtime 4ms, beating 81% of submissions.

    class Solution {
        
        public String countAndSay(int n) {
            String s = "1";
            for (int i = 1; i<n; i++) s = countAndSay (s);
            return s;
        }
        
        public String countAndSay (String s) {
            int counter = 1;
            String result = "";
            for(int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == s.charAt(i-1)) counter++;
                else {
                    result = result + counter + s.charAt(i-1);
                    counter = 1;
                }
            }
            result = result + counter + s.charAt(s.length()-1);
            return result;
        }
    }
    

    and StringBuilder version of countAndSay (String s) method:

    public String countAndSay (String s) {
            int counter = 1;
            StringBuilder result = new StringBuilder();
            for(int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == s.charAt(i-1)) counter++;
                else {
                    result.append(counter);
                    result.append(s.charAt(i-1));
                    counter = 1;
                }
            }
            result.append(counter);
            result.append(s.charAt(s.length()-1));
            return result.toString();
        }
    

Log in to reply
 

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