This post is completed by 1 user

  • 1
 Add to List
Beginner

562. Merge Strings Alternately - Leetcode

Problem Statement

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If one string is longer than the other, append the additional letters onto the end of the merged string.

Constraints:

  • 1 <= word1.length, word2.length <= 100
  • word1 and word2 consist of lowercase English letters.

Examples

Input:
word1 = abc, word2 = pqr
Output: apbqcr
Input:
word1 = abcd, word2 = pq
Output: apbqrs
Input:
word1 = ab, word2 = pqrs
Output: apbqcd

Solution

  1. Initialize an empty list merged to store the resulting characters.
  2. Use two pointers i and j to track positions in word1 and word2.
  3. Iterate through word1 and word2 simultaneously, appending characters alternately.
  4. If any characters remain in word1 or word2, append them directly to the result.
  5. Convert the list to a string and return the result.

Complexity Analysis

  • Time Complexity: O(n + m), where n and m are the lengths of word1 and word2, respectively. We iterate through both strings once.
  • Space Complexity: O(n + m), since we store the merged string in a list before joining.

Related Problems: