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