[LeetCode][C++]1768. Merge String Alternately(String)

❓Question

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

• 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.

---

Intuition

The problem asks to merge two strings alternately.
Therefore, we can traverse both strings at the same time and pick each character alternately from both strings.

Approach

1. Initialize an empty string to store the merged result.
2. Traverse both input strings together, picking each character alternately from both strings and appending it to the merged result string.
3. Continue the traversal until the end of the longer string is reached.
4. Return the merged result string.

Complexity

• Time complexity:

  Since we traverse both strings once and pick each character alternately, the time complexity of this approach is O(n), where n is the length of the longer string.

• Space complexity:

  We use a StringBuilder to store the merged string, so the space complexity of this approach is O(n), where n is the length of the longer string.

💻Solution

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        // 단어 길이가 더 짧은 단어 기준으로 번갈아가면서 문자를 합침
        int minSize = word1.length() <= word2.length() ? word1.length() : word2.length();
        string longerStr = word1.length() <= word2.length() ? word2 : word1;

        string answer = "";
        answer.reserve(word1.length() + word2.length()); // 미리 메모리 확보

        for (int i = 0; i < minSize; i++)
        {
            answer.push_back(word1[i]); // 효율적으로 문자 추가
            answer.push_back(word2[i]);
        }  

        // 나머지 부분을 split해서 뒤에 붙임  
        if(longerStr.length() > minSize)  answer.append(longerStr.substr(minSize));

        return answer;
    }
};

• Complexity
  • Time: O(N+M)
  • Space: O(1)