Optimizing String Concatenation with StringBuilder

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Imagine you want to concatenate a large number of strings together. Assuming the strings are all the same length x and there are n strings, it takes $O(x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx)$O(x+2x+...+nx) time. On each concatenation, we create a copy of the previous string and copy over the new string. Thus, the first iteration would require copying x characters. The next iteration would require copying 2x characters, and so on.

We can actually simplify the previously stated runtime further:

$$x+2x+\mathrm{.}\mathrm{.}\mathrm{.}+nx=x(1+2+\mathrm{.}\mathrm{.}\mathrm{.}+n)=x(\frac{n(n-1)}{2})=x{n}^2$$x+2x+...+nx=x(1+2+...+n)=x(2n(n−1)​)=xn2

Therefore, concatenating strings in this matter takes $O(x{n}^2)$O(xn2) time to complete. Pretty long if you ask me. Here's the algorithm:

function joinWords(words) {
    let sentence = "";
    for (let w of words) {
        sentence = sentence + w;
    }
    return sentence;
}

StringBuilder Class

A StringBuilder class can help you avoid this long runtime. Simply, this class creates a resizable array of all the strings and copies them back to a string only when necessary.

In JavaScript, we can simply use the join method on a resizable array to copy the list of strings into a string.

function joinWords(words) {
    let sentence = [];
    for (let w of words) {
        sentence.push(w);
    }

    return sentence.join("");
}

Now, appending a string to the array takes $O(1)$O(1) time per operation. The final step of copying the array to a single string takes $O(n)$O(n) time, where n is the number of strings in the array.

The above is the detailed content of Optimizing String Concatenation with StringBuilder. For more information, please follow other related articles on the PHP Chinese website!