23.04.18. 풀었던 문제들

Leetcode 1768. Merge Strings Alternately

 string 2개를 index 하나씩 합치는 문제. merge-sort를 알고 있다면 merge하는 방식으로 쉽게 구현할 수 있다.

// Runtime 2 ms Beats 50.88%
// Memory 6.5 MB Beats 19.57%

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int i = 0, j = 0, len1 = word1.length(), len2 = word2.length();
        string result = "";
        while(i < len1 && j < len2){
            result += word1[i]; i++;
            result += word2[j]; j++;
        }
        while(i < len1){
            result += word1[i]; i++;
        }
        while(j < len2){
            result += word2[j]; j++;
        }
        return result;
    }
};

 

시간복잡도

 word1, word2를 각각 한 번씩 순회하므로 word1 length를 n, word2 length를 m이라 두면 O(n+m)이다.

 

공간복잡도

 result string의 크기는 n+m이므로 O(n+m)