[LeetCode] 792. Number of Matching Subsequences

문제

문자열 s와 문자열 배열 words가 주어질 때, words[i]가 s의 부분 수열(subsequence)인 개수를 반환한다.

부분 수열은 원본 문자열에서 일부 문자를 삭제(0개 가능)하되 남은 문자의 순서는 바꾸지 않고 만든 문자열이다. 예를 들어 "ace"는 "abcde"의 부분 수열이다.

Example 1

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3

Example 2

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints

• 1 <= s.length <= 5 * 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s, words[i]는 소문자 알파벳으로만 구성

1차 풀이 (Time Limit Exceeded)

단어마다 투 포인터로 s를 처음부터 훑는 직관적인 풀이.

function numMatchingSubseq(s: string, words: string[]): number {
    const sLen = s.length;
    let matched = 0;
    for (const word of words) {
        if (sLen < word.length) continue;
        let sIdx = 0;
        let wordIdx = 0;
        while (sIdx < sLen && wordIdx < word.length) {
            if (s[sIdx] === word[wordIdx]) {
                wordIdx++;
            }
            sIdx++;
        }
        if (wordIdx === word.length) {
            matched++;
        }
    }
    return matched;
};

로직은 맞지만 시간 복잡도가 O(words.length * s.length)다. 최악의 경우 5000 * 50000 = 2.5 * 10^8번 비교하게 되어 TLE가 발생한다. 단어 하나를 검사할 때마다 s 전체를 다시 걷는 것이 낭비의 원인이다.

2차 풀이 (Accepted)

s를 한 번만 순회하고, 각 단어가 "다음에 필요한 글자"의 대기열에서 기다리게 한다.

type WordSubseq = {
    word: string;
    idx: number;
};

function numMatchingSubseq(s: string, words: string[]): number {
    const ALPHABET_LENGTH = 26;
    const ALPHABET_START_CODE = 97;
    const alphabet: WordSubseq[][] = Array.from({ length: ALPHABET_LENGTH }, () => []);
    let matched = 0;
    for (const word of words) {
        const charCode = word.charCodeAt(0) - ALPHABET_START_CODE;
        alphabet[charCode].push({ word, idx: 0 });
    }
    for (const char of s) {
        const charCode = char.charCodeAt(0) - ALPHABET_START_CODE;
        const candidates = alphabet[charCode];
        alphabet[charCode] = [];
        for (const { word, idx } of candidates) {
            const nextIdx = idx + 1;
            if (nextIdx === word.length) matched++;
            else alphabet[word.charCodeAt(nextIdx) - ALPHABET_START_CODE].push({ word, idx: nextIdx });
        }
    }
    return matched;
};

동작 방식

1. 알파벳 26개마다 대기열을 만들고, 모든 단어를 자기 첫 글자의 대기열에 넣는다. idx는 그 단어가 현재 기다리는 글자의 위치다.
2. s의 글자를 하나씩 읽는다. 그 글자의 대기열에 있던 단어들만 꺼내서 한 칸 전진시킨다.
3. 전진한 결과 단어 끝에 도달했으면 matched를 올리고, 아니면 다음 글자의 대기열로 옮긴다.
4. s를 다 읽었는데 아직 대기열에 남아 있는 단어는 부분 수열이 아니다.

Example 1로 따라가면, s[0] = 'a'에서 "a"는 완성되고 "acd", "ace"는 c 대기열로 이동한다. s[2] = 'c'에서 둘 다 각각 d, e 대기열로 이동하고, 이후 'd', 'e'를 읽을 때 차례로 완성된다. "bb"는 첫 'b' 이후 두 번째 'b'가 나오지 않아 대기열에 남은 채 끝난다.

복잡도

단어 하나가 대기열을 옮겨 다니는 횟수는 정확히 그 단어의 길이만큼이므로 s의 길이와 무관하다.

• 시간: O(s.length + sum(words[i].length))
• 공간: O(words.length)