String Interleaving Algorithm

Given two strings s0 and s1, return the two strings interleaved, starting with s0. If there are leftover characters in a string they should be added to the end.

Constraints
n ≤ 100,000 where n is the length of s0
m ≤ 100,000 where n is the length of s1
Example 1
Input
s0 = “abc”
s1 = “xyz”
Output
“axbycz”
Example 2
Input
s0 = “abc”
s1 = “x”
Output
“axbc”

Interleaved String Algorithm by Two Pointer

We can append one letter/character from each string at a time, and concatenate with the rest (the longer one). The C++ code to implement this using two pointers:

string stringInterleaving(string s0, string s1) {
    string ans = "";
    int i = 0, j = 0;
    while (i < s0.size() && j < s1.size()) {
        ans += s0[i];
        ans += s1[j];
        i ++;
        j ++;
    }
    if (i < s0.size()) ans += s0.substr(i);
    if (j < s1.size()) ans += s1.substr(i);
    return ans;
}

Actually, we can just use one counter and a better implementation in Python is:

class Solution:
    def stringInterleaving(self, s0, s1):
        ans = []
        i = 0
        while i < len(s0) and i < len(s1):
            ans.append(s0[i])
            ans.append(s1[i])
            i += 1
        ans.append(s0[i:])
        ans.append(s1[i:])
        return "".join(ans)

In Python, we can rely on the zip_longest, but make sure we avoid concatenating the None.

class Solution:
    def stringInterleaving(self, s0, s1):
        def f(a, b):
            if a is None:
                return b
            if b is None:
                return a
            return a + b
        return "".join(f(x[0], x[1]) for x in zip_longest(list(s0), list(s1)))

All implemenations are in O(A+B) time and O(A+B) space where A and B are the length of both strings respectively.

See GoLang Implementation of Merge Strings Alternatively: GoLang: Merge Strings Alternately

–EOF (The Ultimate Computing & Technology Blog) —