1768. Merge Strings Alternately

EasyView on LeetCode

Two Pointers String

Time: O(m+n)

Space: O(m+n)

Problem Overview

Merge word1 and word2 by alternating characters.

Intuition

Merge word1 and word2 by alternating characters. When one string runs out, append the rest of the other. Two pointers walk both strings in lockstep.

Algorithm

1Initialize i = 0, j = 0 and empty result.
2While i < word1.Length && j < word2.Length: append word1[i], then word2[j]; i++, j++.
3Append remaining characters from whichever string is not exhausted.
4Return merged string.

Example Walkthrough

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

1.Merge a,p,b,q,c,r → "apbqcr".

Output: "apbqcr"

Common Pitfalls

•Alternate starting with word1 first.
•Do not forget the tail of the longer string.
•O(n+m) time, O(n+m) output space.

1768.cs

// Approach: Two-pointer alternating append, then append remainder of whichever string is longer.
// Time: O(m+n) Space: O(m+n)

public class Solution
{
    public string MergeAlternately(string word1, string word2)
    {
        int l1 = 0, l2 = 0;
        int r1 = word1.Length;
        int r2 = word2.Length;

        StringBuilder res = new StringBuilder();
        while (l1 < r1 && l2 < r2)
        {
            res.Append(word1[l1++]);
            res.Append(word2[l2++]);
        }

        while (l1 < r1)
            res.Append(word1[l1++]);

        while (l2 < r2)
            res.Append(word2[l2++]);

        return res.ToString();
    }
}

Was this solution helpful?