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:
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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; } |
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:
1 2 3 4 5 6 7 8 9 10 11 | 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) |
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.
1 2 3 4 5 6 7 8 9 | 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))) |
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) —
loading...
Last Post: Teaching Kids Programming - Ugly Number Detection Algorithm
Next Post: Teaching Kids Programming - Recursive Depth First Search Algorithm to Compare Leaf Equivalent Trees
