Optimizing String Concatenation with StringBuilder

This content originally appeared on DEV Community and was authored by Terrence Jung

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 + 2 x + ... + n x)$ 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(\frac{n(n-1)}{2}) = xn^2

Therefore, concatenating strings in this matter takes $O(xn^2)$ 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)$ time per operation. The final step of copying the array to a single string takes $O (n)$ time, where n is the number of strings in the array.

This content originally appeared on DEV Community and was authored by Terrence Jung

Print Share Comment Cite Upload Translate Updates

APA

Terrence Jung | Sciencx (2024-07-30T00:05:20+00:00) Optimizing String Concatenation with StringBuilder. Retrieved from https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/

MLA

" » Optimizing String Concatenation with StringBuilder." Terrence Jung | Sciencx - Tuesday July 30, 2024, https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/

HARVARD

Terrence Jung | Sciencx Tuesday July 30, 2024 » Optimizing String Concatenation with StringBuilder., viewed ,<https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/>

VANCOUVER

Terrence Jung | Sciencx - » Optimizing String Concatenation with StringBuilder. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/

CHICAGO

" » Optimizing String Concatenation with StringBuilder." Terrence Jung | Sciencx - Accessed . https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/

IEEE

" » Optimizing String Concatenation with StringBuilder." Terrence Jung | Sciencx [Online]. Available: https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/. [Accessed: ]

rf:citation

» Optimizing String Concatenation with StringBuilder | Terrence Jung | Sciencx | https://www.scien.cx/2024/07/30/optimizing-string-concatenation-with-stringbuilder/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

StringBuilder Class

Related Posts