LeetCode 1768. Merge Strings Alternately (Easy)

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.

Input 1: word1 = "abc", word2 = "pqr"
Output 1: "apbqcr"

Input 2: word1 = "ab", word2 = "pqrs"
Output 2: "apbqrs"

Think with me:

• Here, we have two words (word1 and word2).
• We will create a res array to store the result.
• We will create two pointers or two variables: p1 for word1 and p2 for word2.
• Then, we will write a while loop that will run until the length of p1 is less than length of word1 and the length of p2 is less than the length of word 2
• For each iteration of the while loop, we will append (insert) the character from word1[p1] into the res array. And we will repeat the same for word2[p2] as well.
• After inserting one each character from word1 and word2, we will move the pointer forward (or in other words, increase the value of p1 and p2 each by 1).
• After the while loop finishes, we check if there are any extra characters in word1 and word2 which were not covered by the while loop. If there are, we append or insert the remaining characters into res
• After finishing the above steps, we will convert the res array into a string because the qeustions asks us to return the merged string

Python Code

Here is the python code for the problem:

def mergeAlternately(word1, word2):
        p1, p2 = 0, 0
        l1, l2 = len(word1), len(word2)
        res = []
        while p1 < l1 and p2 < l2:
            res.append(word1[p1])
            res.append(word2[p2])
            p1 += 1
            p2 += 1
        res.append(word1[p1:])
        res.append(word2[p2:])

    return "".join(res)

LeetCode Link

Time Complexity:

• Since, we are traversing all the characters of word1 and word2, the time complexity is: O(n + m) where n is the number of characters in word1 and m is the number of characters in word2

Space Complexity:

• We are creating a new array or list called res to store all the characters from word1 and word2.
• Therefore, the space complexity is: O(n + m) where n is the number of characters in word1 and m is the number of characeters in word2.

Practical Tips

• Take a pen and paper
• Walk through the code by writing it
• Literally, write each iteration of the array and see how the pointers p1 and p2 move while inserting each character in the res list or aray.
• Don't worry if you were not able to solve this question at all, it happens to someone. We all start somewhere. Cheer up!

Conclusion

Write the code and each iteration on a paper. Revise it the next day.

Even if you are not able to solve anything, just do it everyday. Use pen and paper everyday. A day will come when you finally have that algorithmic satisfaction!