1768. Merge Strings Alternately
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 75.8%
Problem Breakdown
The problem requires merging two given strings, word1 and word2, by alternating their characters. The process starts with the first character of word1, followed by the first character of word2, then the second character of word1, and so on. If one string is longer than the other, the remaining characters of the longer string are appended to the end of the merged result.
Inputs:
- Two strings,
word1andword2.
Output:
- A single merged string with characters from
word1andword2alternated.
Implicit Constraints/Edge Cases:
- If either or both strings are empty.
- The lengths of the strings can be different.
Intuition
A brute-force approach would involve iterating through each character of both strings simultaneously, appending them to a result string. However, this approach could lead to inefficient handling of cases where one string is significantly longer than the other, resulting in unnecessary iterations.
The key insight is to use two pointers to traverse both strings and append characters alternately until we reach the end of one of the strings. After that, we can simply append the remaining characters from the longer string.
Approach
- Initialize an empty list
mergedto store the merged characters. - Use two pointers,
iandj, initialized to 0, to traverseword1andword2, respectively. - While both pointers are within the bounds of their respective strings:
- Append the character at position
ifromword1tomerged. - Append the character at position
jfromword2tomerged. - Increment both pointers by 1.
- Append the character at position
- After exiting the loop, append any remaining characters from either
word1orword2tomerged. - Join the list
mergedinto a single string and return it.
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of
word1and m is the length ofword2. This is because we iterate through each character of both strings once. - Space Complexity: O(n + m) for storing the merged result. The space used by the pointers and other variables is constant.
Solution
def mergeAlternately(word1, word2):
merged = []
i, j = 0, 0
# Traverse both strings alternately
while i < len(word1) and j < len(word2):
merged.append(word1[i])
merged.append(word2[j])
i += 1
j += 1
# Append remaining characters from word1, if any
while i < len(word1):
merged.append(word1[i])
i += 1
# Append remaining characters from word2, if any
while j < len(word2):
merged.append(word2[j])
j += 1
return ''.join(merged)
Edge Cases Handled
- Empty Strings: If either
word1orword2is empty, the function will correctly handle it by appending only the non-empty string. - Unequal Lengths: The function appends any remaining characters from the longer string after one of the strings is fully traversed.