Why is this code with StringBuilder slower than the same code using String?


  • 0
    T

    This is my accepted solution with StringBuilder.

    private String[] keys = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};    
    
    public void DFS(String digits, List<String> ret, int currIndex, StringBuilder currString) {
        if (currIndex == digits.length()) {
            ret.add(currString.toString());
            return;
        }
        String key = keys[Integer.parseInt(String.valueOf(digits.charAt(currIndex))) - 2];
        for (int i = 0; i < key.length(); i++) {
            DFS(digits, ret, currIndex + 1, currString.append(key.charAt(i)));
            currString.deleteCharAt(currString.length() - 1);
        }
    }
    
    
    public List<String> letterCombinations(String digits) {
        List<String> ret = new LinkedList<String>();
        DFS(digits, ret, 0, new StringBuilder(""));
        return ret;
    }
    

    And this is my code with Strings.

    private String[] keys = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public void DFS(String digits, List<String> ret, int currIndex, String currString) {
        if (currIndex == digits.length()) {
            ret.add(currString);
            return;
        }
        String key = keys[Integer.parseInt(String.valueOf(digits.charAt(currIndex))) - 2];
        for (int i = 0; i < key.length(); i++) {
            DFS(digits, ret, currIndex + 1, currString + key.charAt(i));
        }
    }
    
    public List<String> letterCombinations(String digits) {
        List<String> ret = new LinkedList<String>();
        DFS(digits, ret, 0, "");
        return ret;
    }
    

    They're almost the same. But I got a run time of 232 ms with StringBuilder and a run time of 204 ms. Could someone tell me why there's such a difference? I assumed StringBuilder would work faster, especially since I share the same StringBuilder object across recursive calls. Thanks.


  • 2
    F

    Because we only append ONE character each time, thus, even String append is O(n^2), but while n=1, it is the same of StringBuilder.
    And when you use StringBuilder, you have one more operation which is deleteCharAt(), this method led the main difference between your two solutions.

    wish it can help


  • 0
    F
    This post is deleted!

Log in to reply
 

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