LeetCode: 1768 Merge Strings Alternately

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.

Example:

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

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

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"

问题

给定两个字符串 word1 和 word2。通过交替添加字母来合并字符串，从 word1 开始。如果一个字符串比另一个长，则将附加的字母追加到合并后的字符串末尾。

解决方案 1

使用双指针方法，遍历两个字符串并交替添加字符。

Approach 1 / 方法 1

使用双指针，依次从两个字符串中交替取字符，直到至少一个字符串到达末尾。然后将剩余的字符追加到结果字符串末尾。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Initialize pointers for both strings and an empty result string.
   初始化两个字符串的指针和一个空的结果字符串。

Step 1 / 第一步:

2. Iterate through both strings simultaneously, adding one character from each string to the result string.
   同时遍历两个字符串，从每个字符串中各添加一个字符到结果字符串。

Step 2 / 第二步:

3. Check if there are remaining characters in either string and append them to the result string.
   检查任一字符串是否有剩余字符并将它们追加到结果字符串。

Implementation / 实现

python

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        merged = []
        i, j = 0, 0
        while i < len(word1) and j < len(word2):
            merged.append(word1[i])
            merged.append(word2[j])
            i += 1
            j += 1
        while i < len(word1):
            merged.append(word1[i])
            i += 1
        while j < len(word2):
            merged.append(word2[j])
            j += 1
        return ''.join(merged)

Explanation / 解释

1. Step 1 / 第一步:

• Initialize an empty list merged and two pointers i and j.
  初始化一个空列表 merged 和两个指针 i 和 j。

2. Step 2 / 第二步:

• Traverse both strings using the pointers, adding one character from each string to merged.
  使用指针遍历两个字符串，从每个字符串中各添加一个字符到 merged。

3. Step 3 / 第三步:

• Append any remaining characters from either string to merged.
  将任一字符串中剩余的字符追加到 merged。

Complexity Analysis / 复杂度分析

• Time Complexity: O(M + N), where M and N are the lengths of word1 and word2.
  时间复杂度: O(M + N)，其中 M 和 N 分别是 word1 和 word2 的长度。

• Space Complexity: O(M + N), to store the result.
  空间复杂度: O(M + N)，用于存储结果。

Key Concept / 关键概念

• The key concept is to use two pointers to merge the strings by alternating characters from each string.
  关键概念是使用双指针通过交替添加字符来合并字符串。

解决方案 2

通过递归方法合并字符串。

Approach 2 / 方法 2

使用递归方法，在递归过程中依次从两个字符串中取字符。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Define a recursive function to merge strings alternately.
   定义一个递归函数来交替合并字符串。

Step 1 / 第一步:

2. In each recursive call, add one character from each string to the result.
   在每次递归调用中，从每个字符串中各添加一个字符到结果。

Step 2 / 第二步:

3. Recur with the remaining parts of the strings.
   用剩余部分的字符串进行递归。

Implementation / 实现

python

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        if not word1:
            return word2
        if not word2:
            return word1
        return word1[0] + word2[0] + self.mergeAlternately(word1[1:], word2[1:])

Explanation / 解释

1. Step 1 / 第一步:

• Base case: if one string is empty, return the other string.
  基本情况：如果一个字符串为空，则返回另一个字符串。

2. Step 2 / 第二步:

• Add the first character of both strings to the result and recur for the remaining parts of the strings.
  将两个字符串的第一个字符添加到结果中，并对字符串的剩余部分进行递归。

Complexity Analysis / 复杂度分析

• Time Complexity: O(M + N)
  时间复杂度: O(M + N)

• Space Complexity: O(M + N)
  空间复杂度: O(M + N)

Key Concept / 关键概念

• The key concept is to use recursion to merge strings by alternating characters.
  关键概念是使用递归通过交替添加字符来合并字符串。

Tips / 提示

• Ensure that you handle cases where one string is longer than the other.
  确保处理一个字符串比另一个字符串长的情况。

Solution Template for similar questions / 提示

• The approach can be applied to other problems involving merging or interleaving two sequences.
  该方法可以应用于涉及合并或交错两个序列的其他问题。

Recommended 5 more similar questions to help user practice / 推荐5问题

1. LeetCode 921: Minimum Add to Make Parentheses Valid
2. LeetCode 1089: Duplicate Zeros
3. LeetCode 1764: Form Array by Concatenating Subarrays of Another Array
4. LeetCode 88: Merge Sorted Array
5. LeetCode 986: Interval List Intersections

Recommended more online resource to help user practice.

• LeetCode Explore – String
• GeeksforGeeks – String Data Structure
• InterviewBit – String Interview Questions
• Leetcode 75

More

zip_longest function

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        return ''.join(a + b for a, b in zip_longest(word1, word2, fillvalue=''))

Purpose of the Code

The purpose of this function mergeAlternately is to take two strings, word1 and word2, and merge them by alternating characters from each string. If one string is shorter, the remaining characters from the longer string are appended to the result.

Breakdown of the Code

1. Function Definition:

   def mergeAlternately(self, word1: str, word2: str) -> str:

   • mergeAlternately is a method of the Solution class.
   • It takes two arguments, word1 and word2, both of which are expected to be strings (str).
   • The method returns a string, as indicated by the return type annotation -> str.

2. Using zip_longest:

   return ''.join(a + b for a, b in zip_longest(word1, word2, fillvalue=''))

   • The zip_longest function is imported from the itertools module, which is not shown here but is a standard Python library function.
   • zip_longest is similar to the zip function, but it can handle input iterables (like strings) of different lengths.
   • When using zip, if the input iterables are of unequal lengths, it stops when the shortest iterable is exhausted. However, zip_longest continues until the longest iterable is exhausted, filling in the missing values with a specified fillvalue.

3. Merging the Strings:

   • The expression zip_longest(word1, word2, fillvalue='') pairs elements from word1 and word2.
   • If word1 is longer than word2, the remaining characters of word1 will be paired with the fillvalue, which is an empty string ''.
   • Similarly, if word2 is longer than word1, its remaining characters will be paired with ''.

4. Generating the Result:

   • The list comprehension a + b for a, b in zip_longest(word1, word2, fillvalue='') iterates over the paired elements returned by zip_longest.
   • For each pair (a, b), it concatenates a and b.
   • These concatenated pairs are then joined together into a single string using ''.join(...).

5. Return Value:

   • The final result is a string where characters from word1 and word2 are alternated. If one string is shorter, the remaining characters from the longer string are added at the end.

Example

Let’s go through an example to see how this works in practice.

word1 = "abc"
word2 = "defgh"

• zip_longest(word1, word2, fillvalue='') will generate:

  ('a', 'd'), ('b', 'e'), ('c', 'f'), ('', 'g'), ('', 'h')

• The list comprehension generates:

  'ad', 'be', 'cf', 'g', 'h'

• Finally, ''.join(...) concatenates these strings into:

  "adbecfgh"

So, the result of mergeAlternately("abc", "defgh") is "adbecfgh".

Key Concepts

1. zip_longest: This function is crucial for handling cases where the input strings have different lengths, ensuring that no characters are left out in the final merged string.
2. String Concatenation: The approach effectively combines characters from both strings, ensuring the desired alternating pattern.
3. Edge Cases: The code handles cases where one or both strings might be empty, thanks to the use of fillvalue='' in zip_longest.

Final Thoughts

This method provides an elegant and concise way to merge two strings alternately, using Python’s powerful itertools.zip_longest function and string manipulation techniques. The code is efficient and handles edge cases well, making it a robust solution for the problem at hand.

Recommend Resource:

Merge Strings Alternately – Leetcode 1768 – Python by NeetCodeIO