Leetcode – Merge Strings Alternately Solution

Spread the love

The “Merge Strings Alternately” problem is a LeetCode problem that involves basic string manipulation and concatenation. It’s a problem that can be approached in different ways, ranging from simple solutions to slightly more optimized ones.

This article aims to guide you through multiple ways to solve this problem using Python. We will discuss the problem statement, several approaches to solving the problem, and we’ll analyze the time and space complexities of each solution.

Problem Statement

Given two strings word1 and word2, merge them in the following way:

1. Begin with the first character of word1 and append it to the result.
2. Append the first character of word2 to the result.
3. Append the second character of word1 to the result.
4. Append the second character of word2 to the result.
5. And so on, until one of the strings is exhausted.
6. Append the remaining characters of the longer string to the result.

Return the merged string.

Examples

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: The merged string will be merged as so:
word1:  a   b
word2:    p   q   r   s
merged: a p b q r s

Approach 1: Brute Force

The simplest approach to solving this problem is to manually alternate between appending characters from word1 and word2 to a new string until one of the strings is exhausted, then appending the remaining characters from the longer string.

Algorithm Steps

1. Initialize an empty string result to store the merged string.
2. Loop through both strings until one is exhausted.
3. In each loop iteration, append one character from word1 and one from word2 to result.
4. Append the remaining characters from the longer string to result.

Python Code

def mergeAlternately(word1, word2):
result = []
i, j = 0, 0
while i < len(word1) and j < len(word2):
result.append(word1[i])
result.append(word2[j])
i += 1
j += 1
while i < len(word1):
result.append(word1[i])
i += 1
while j < len(word2):
result.append(word2[j])
j += 1
return ''.join(result)

Time and Space Complexity

• Time Complexity: O(n+m), where n and m are the lengths of word1 and word2.
• Space Complexity: O(n+m) for storing the result.

Approach 2: Using Python’s zip_longest function

Python’s itertools library provides a function called zip_longest which can make our job easier.

Algorithm Steps

1. Use zip_longest to pair characters from word1 and word2.
2. For each pair, append the non-None characters to result.

Python Code

from itertools import zip_longest

def mergeAlternately(word1, word2):
result = []
for ch1, ch2 in zip_longest(word1, word2, fillvalue=''):
result.append(ch1)
result.append(ch2)
return ''.join(result).replace("None", "")

Time and Space Complexity

• Time Complexity: O(n+m)
• Space Complexity: O(n+m)

Approach 3: Optimizing Memory Usage

If we want to optimize for space, we can make use of Python’s string immutability and perform string concatenation in place without creating a new list for result.

Python Code

def mergeAlternately(word1, word2):
result = ''
i, j = 0, 0
while i < len(word1) and j < len(word2):
result += word1[i] + word2[j]
i += 1
j += 1
while i < len(word1):
result += word1[i]
i += 1
while j < len(word2):
result += word2[j]
j += 1
return result

Time and Space Complexity

• Time Complexity: O(n+m)
• Space Complexity: O(n+m) for storing the result string, but less memory overhead compared to storing a list.

Conclusion

The “Merge Strings Alternately” problem is a great exercise in basic string manipulation and data structure use in Python. We’ve explored multiple solutions to this problem, each with its own advantages and disadvantages. The problem itself is relatively straightforward but is a great way to learn or review important Python functionalities like zip_longest and also serves as a good introduction to time and space complexity analysis.