Description

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr" Output: "apbqcr" Explanation: The merged string will be merged as so: word1: a b c word2: p q r merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs" Output: "apbqrs" Explanation: Notice that as word2 is longer, "rs" is appended to the end. word1: a b word2: p q r s merged: a p b q r s

Example 3:

Input: word1 = "abcd", word2 = "pq" Output: "apbqcd" Explanation: Notice that as word1 is longer, "cd" is appended to the end. word1: a b c d word2: p q merged: a p b q c d

Constraints:

• 1 <= word1.length, word2.length <= 100
• word1 and word2 consist of lowercase English letters.

Solution

My first instinct to approaching this problem was to brute force it. I'd iterate through the strings and add each letter from both strings to an empty string (merge) until both strings have been fully iterated through.

function mergeAlternately(word1: string, word2: string): string {
    let merge: string = "";
    let pos: number = 0;

    while ((word1.length > pos) || (word2.length > pos)) {
        if (word1[pos]) {
            merge += word1[pos];
        }        
        if (word2[pos]) {
            merge += word2[pos];
        }

        pos++;
    }

    return merge;
};

This code had a runtime of 76 ms and memory usage of 53 MB.

While this approach worked I was not very satisfied, so I thought about what I could do to improve this. There were two key changes that affected my runtime.

1. I switched from using a string, to using an array to hold my alternating letters. I learned that pushing to an array, was faster than altering a string. This is because while arrays are mutable, strings are not. What is happening in the background whenever you modify a string is that a new string is actually being created. So despite having to join all my letters at the end in order to return a string, using an array made a significant improvement in runtime and memory usage.
2. I only iterated until the position of the shortest string. I realized that if one string was significantly longer than the other string, there is no need to continue checking if a letter exists past the last position of the shorter string. I could simply add the remainder of the longer string after joining the merge array.

function mergeAlternately(word1: string, word2: string): string {
    let merge = [];
    let pos: number = 0;

    while ((word1.length > pos) && (word2.length > pos)) {
        merge.push(word1[pos])
        merge.push(word2[pos]);

        pos++;
    }

    if (word1.length > word2.length) {
        return merge.join('') + word1.slice(pos);
    } else {
        return merge.join('') + word2.slice(pos);
    }
};

The changes helped bring my runtime down to 48ms.