GoLang: 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.

GoLang Algorithm to Merge Strings Alternatively

Let’s keep two pointers, and concatenate characters one by one alternatively from two strings.

1
2
3
4
5
6
7
8
9
10
11
12
13

func mergeAlternately(word1 string, word2 string) string {
    var l1, l2 = len(word1), len(word2)
    var ans = ""
    for i, j := 0, 0; i < l1 || j < l2; i, j = i + 1, j + 1 {
        if i < l1 {
            ans += string(word1[i])
        }
        if j < l2 {
            ans += string(word2[j])
        }
    }
    return ans
}

func mergeAlternately(word1 string, word2 string) string {
    var l1, l2 = len(word1), len(word2)
    var ans = ""
    for i, j := 0, 0; i < l1 || j < l2; i, j = i + 1, j + 1 {
        if i < l1 {
            ans += string(word1[i])
        }
        if j < l2 {
            ans += string(word2[j])
        }
    }
    return ans
}

GoLang implementation: O(N+M) time where N and M are the lengths of two strings respectively. The space complexity is also O(N+M) as we are allocating a new string (result).

See also: String Interleaving Algorithm

–EOF (The Ultimate Computing & Technology Blog) —