Solution 1
func mergeAlternately(word1 string, word2 string) string {
resStr := ""
w1Len := len(word1)
w2Len := len(word2)
for i:=0;i<max(w1Len,w2Len);i++{
if i<w1Len{
resStr+=string(word1[i])
}
if i<w2Len{
resStr+=string(word2[i])
}
}
return resStr
}

Solution 2
func mergeAlternately(word1 string, word2 string) string {
resStr := ""
w1Len := len(word1)
w2Len := len(word2)
for i:=0;i<min(w1Len,w2Len);i++{
resStr+=string(word1[i])
resStr+=string(word2[i])
}
if w1Len<w2Len{
resStr+=word2[w1Len:]
} else {
resStr+=word1[w2Len:]
}
return resStr
}

Time Complexity – O(m+n)
It appears to be O(min(m,n)) because the loop will only for shorter string length but string concatenation causes the string’s underlying array (i.e resStr) to reallocate and move data, so effectively in worst case it should take complete length of resStr
Space Complexity – O(m+n)
All allocations except resStr are O(1) and resStr takes a total length of both input strings combined
Leave a Reply