1768. Merge Strings Alternately

[songyy5517]

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

Intuition This problem mainly examines the operations of String. A straightforward idea is that set up two pointers to travarse two strings alternatively and then use a StringBuffer to receive the character in these strings. Another point is that when one string goes out of range, we should not iterate over it anymore, but just the other one.

[songyy5517]

Approach: The traverse and concatenation of String

1. Exception handling;
2. Define variables: two pointers, StringBuffer;
3. Traverse two strings when one of the pointers is not out of range: (1) If pointer 1 is within the range, add the character in word1 to StringBuffer, update pointer 1; (2) If pointer 2 is within the range, add the character in word2 to StringBuffer, update pointer 2;
4. Convert StringBuffer into String, and return.

Complexity Analysis

• Time complexity: $O(M+N)$ , travarsing two strings costs the time of $O(M+N)$ ;
• Space complexity: $O(M+N)$ , additionally define StringBuffer to store the final reseult which has a space of $O(M+N)$.

[songyy5517]

class Solution {
    public String mergeAlternately(String word1, String word2) {
        // 1. Exceptions
        if (word1 == null || word2 == null)
            return word1 == null ? word2 : word1;

        // 2. Define StringBuffer
        StringBuffer sb = new StringBuffer();
        int p1 = 0, p2 = 0;

        while (p1 < word1.length() || p2 < word2.length()){
            if (p1 < word1.length()){
                sb.append(word1.charAt(p1));
                p1 ++;
            }

            if (p2 < word2.length()){
                sb.append(word2.charAt(p2));
                p2 ++;
            }
        }

        return sb.toString();
    }
}

[songyy5517]

2024/5/6