Leetcode problem 95 - 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.

Return the merged string.

Example 1:

Input: word1 = “abc”, word2 = “pqr” Output: “apbqcr” Explanation: The merged string will be merged as so: word1: a b c word2: p q r merged: a p b q c r Example 2:

Input: word1 = “ab”, word2 = “pqrs” Output: “apbqrs” Explanation: Notice that as word2 is longer, “rs” is appended to the end. word1: a b word2: p q r s merged: a p b q r s Example 3:

Input: word1 = “abcd”, word2 = “pq” Output: “apbqcd” Explanation: Notice that as word1 is longer, “cd” is appended to the end. word1: a b c d word2: p q merged: a p b q c d

Constraints:

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

/**
 * @param {string} word1
 * @param {string} word2
 * @return {string}
 */
var mergeAlternately = function (word1, word2) {
  // Initialize an array to store the merged characters
  const merged = [];

  // Initialize pointers for each word
  let left = 0;
  let right = 0;

  // Continue merging until at least one of the words is fully processed
  while (left < word1.length || right < word2.length) {
    // If there are remaining characters in word1, add them to merged
    if (word1[left]) {
      merged.push(word1[left]);
      left++;
    }

    // If there are remaining characters in word2, add them to merged
    if (word2[right]) {
      merged.push(word2[right]);
      right++;
    }
  }

  // Join the merged array into a single string and return the result
  return merged.join("");
};

Time Complexity: The time complexity of this code is O(max(n, m)), where n is the length of word1 and m is the length of word2. The loop iterates until at least one of the words is fully processed.

Space Complexity: The space complexity is O(n + m), where n is the length of word1 and m is the length of word2. The additional space is used to store the characters in the merged array. In the worst case, both words are fully merged into the merged array.