23.04.18. 문제 해결

by

Leetcode 1768. 교대로 문자열 병합

두 개의 문자열을 하나의 인덱스로 결합하는 문제입니다.

병합 정렬을 알면 병합 방식으로 쉽게 구현할 수 있습니다.

// 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;
    }
};

시간 복잡도

워드1과 워드2는 각각 1회씩 순회하므로 워드1의 길이가 n이고 워드2의 길이가 m이면 O(n+m)이다.

공간 복잡성

결과 문자열의 크기는 n+m이므로 O(n+m)

'추천 관련글,