sudopower

lc_1768

LC: 1768: Merge Strings Alternatively

 

Link to problem

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

Your email address will not be published. Required fields are marked *

Related Blogs