1768. Merge Strings Alternately

EasyTwo PointersString
Leetcode Link

Problem Description

In this problem, you are given two input strings, word1 and word2. Your task is to combine these two strings into a new string, by alternating characters from each. You start merging from word1, then word2, and repeat this process until you use all characters from both strings. If one string is longer than the other, you simply continue adding the remaining characters from the longer string to the end of the merged string. The goal is to return the merged string as the result.

Intuition

The intuition behind the solution involves iterating through both strings concurrently and pairing up characters to the new string. A key point is determining what to do when the strings are of different lengths. One approach is to use the zip function that pairs elements from both strings. However, zip stops when the shortest input is exhausted. To overcome this, we can use the zip_longest function from Python's itertools module, which allows pairing beyond the length of the shorter word by filling in missing values with a specified value (fillvalue='' in this case, which represents an empty string).

The function zip_longest(word1, word2, fillvalue='') pairs corresponding characters from each string and fills in with an empty string when either word1 or word2 runs out of characters. We join these pairs using a generator expression that concatenates each pair of characters into a single string, accounting for the possibility of one character being an empty string when the other string has extra characters. We then use ''.join() on this sequence to merge all pairs into the final merged string.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used in a depth first search?

Solution Approach

The solution leverages Python's itertools.zip_longest function to iterate over both input strings word1 and word2 in parallel. This function can handle input sequences of different lengths by filling in missing values with a specified value ('' in this case).

Here's a step-by-step explanation of the algorithm:

  1. We call the zip_longest function with word1, word2, and fillvalue='' to create an iterator that pairs elements from both word1 and word2. If one string is shorter than the other, zip_longest will use the fillvalue to ensure that the iterator can still return pairs of values until the longer string is fully processed.

  2. We use a generator expression (a + b for a, b in zip_longest(word1, word2, fillvalue='')) which goes through each pair produced by zip_longest and concatenates the elements of each pair. This handles the alternating of characters from word1 and word2 and takes care of any additional characters from the longer string.

  3. Finally, ''.join() is called on the generator expression to concatenate all string pairs into a single string without any separators. This results in the merged string that comprises characters from word1 and word2 in alternating order, fulfilling the requirements laid out in the problem description.

This solution elegantly utilizes the zip_longest to abstract away the complexity of dealing with different string lengths and allows the process to be expressed in a single, readable, and efficient line of code.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider two example input strings for our walk-through:

  • word1 = "Hello"
  • word2 = "World"

Applying the solution approach:

  1. We call zip_longest(word1, word2, fillvalue=''), which pairs H with W, e with o, l with r, l with l, and o with d. Since word1 and word2 are of equal length, fillvalue='' is not utilized here.

  2. As we go through the generator expression (a + b for a, b in zip_longest(word1, word2, fillvalue='')), it yields 'HW', 'eo', 'lr', 'll', and 'od'.

  3. By calling ''.join() on the generator expression, we concatenate all these string pairs to form the final merged string: 'HW' + 'eo' + 'lr' + 'll' + 'od' which results in "HWeorlld", achieving an alternating character string using elements from both word1 and word2.

This example clearly demonstrates how each step of the process works in unison to solve the problem, even when the strings are of equal length, and the method remains robust for strings of differing lengths as well.

Solution Implementation

1from itertools import zip_longest  # Importing zip_longest from itertools for handling uneven iterables
2
3class Solution:
4    def merge_alternately(self, word1: str, word2: str) -> str:
5        # This method merges two strings alternately, filling in with an empty string if one is shorter
6      
7        # Use itertools' zip_longest to pair up characters from both strings. If one string is shorter, fill the missing values with ''.
8        # Join the paired characters into a single string with list comprehension and join method.
9        merged_string = ''.join(a + b for a, b in zip_longest(word1, word2, fillvalue=''))
10      
11        return merged_string  # Return the resulting merged string
12
1class Solution {
2    // Method to merge two strings alternately.
3    public String mergeAlternately(String word1, String word2) {
4        // Length of the first and second words
5        int lengthWord1 = word1.length(), lengthWord2 = word2.length(); 
6        // StringBuilder to create the result string efficiently
7        StringBuilder mergedString = new StringBuilder(); 
8      
9        // Iterate as long as we have characters remaining in at least one string
10        for (int index = 0; index < lengthWord1 || index < lengthWord2; ++index) {
11            // If the current index is within the bounds of word1, append its character
12            if (index < lengthWord1) {
13                mergedString.append(word1.charAt(index));
14            }
15            // If the current index is within the bounds of word2, append its character
16            if (index < lengthWord2) {
17                mergedString.append(word2.charAt(index));
18            }
19        }
20        // Return the resulting string
21        return mergedString.toString();
22    }
23}
24
1class Solution {
2public:
3    // Function to merge two strings alternately
4    string mergeAlternately(string word1, string word2) {
5        int length1 = word1.size(); // length of the first word
6        int length2 = word2.size(); // length of the second word
7        string result; // string to store the result of merging
8
9        // Loop through the maximum length of the two strings
10        for (int i = 0; i < max(length1, length2); ++i) {
11            // If the current index is less than the length of word1, append the character to result
12            if (i < length1) result += word1[i];
13            // If the current index is less than the length of word2, append the character to result
14            if (i < length2) result += word2[i];
15        }
16
17        return result; // Return the merged string
18    }
19};
20
1function mergeAlternately(word1: string, word2: string): string {
2    // Initialize an array to hold the results of the merge.
3    const mergedArray: string[] = [];
4  
5    // Determine the longer length from both words.
6    const maxLength: number = Math.max(word1.length, word2.length);
7  
8    // Loop through each character up to the maximum length.
9    for (let index = 0; index < maxLength; index++) {
10        // If the current index is within the range of word1, push the character into mergedArray.
11        if (index < word1.length) {
12            mergedArray.push(word1[index]);
13        }
14        // If the current index is within the range of word2, push the character into mergedArray.
15        if (index < word2.length) {
16            mergedArray.push(word2[index]);
17        }
18    }
19  
20    // Join the array elements into a string and return the result.
21    return mergedArray.join('');
22}
23
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

The time complexity of the code is O(max(M, N)), where M is the length of word1 and N is the length of word2. This complexity arises because the code iterates through both strings simultaneously until the end of the longer string is reached, making use of zip_longest. At each step of iteration, it performs a constant amount of work by concatenating a single character or an empty string (represented by fillvalue='' when one of the inputs is exhausted).

The space complexity is also O(max(M, N)), primarily due to the output string. The size of the output string will be the sum of the sizes of word1 and word2. In Python, strings are immutable, so each concatenation creates a new string. Since we are using a generator expression with the join method, the space for the intermediate tuples generated by zip_longest is negligible, as they're created and discarded. However, the final string that is returned will have a length equivalent to the sum of the lengths of both input strings, thus leading to the O(max(M, N)) space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫