[LeetCode] 30. Substring with Concatenation of All Words

Map을 생성하여 단어들의 빈도를 미리 확인한다.

슬라이딩 윈도우 기법을 활용하여 특정 길이만큼의 문자열을 탐색해 어떤 인덱스에서 모든 단어가 동일하게 출현되는지 확인한다.

😎풀이

function findSubstring(s: string, words: string[]): number[] {
    // 결과를 저장할 배열
    const result = [];
    
    // words 배열이 비어있으면 빈 배열 반환
    if (words.length === 0) return result;
    
    const wordLength = words[0].length;
    const totalLength = wordLength * words.length;
    
    // words의 각 단어의 출현 횟수를 저장하는 맵
    const wordCount = new Map<string, number>();
    for (const word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }
    
    // sliding window 방식으로 문자열 s를 순회
    for (let i = 0; i <= s.length - totalLength; i++) {
        // 현재 window에서 발견된 단어의 출현 횟수를 저장하는 맵
        const seenWords = new Map<string, number>();
        let j;
        
        // 현재 window 내의 모든 단어를 확인
        for (j = 0; j < words.length; j++) {
            const startIndex = i + j * wordLength;
            const word = s.slice(startIndex, startIndex + wordLength);
            
            // words에 없는 단어를 발견하면 즉시 중단
            if (!wordCount.has(word)) break;
            
            seenWords.set(word, (seenWords.get(word) || 0) + 1);
            
            // 특정 단어가 words에서의 출현 횟수보다 많이 나오면 중단
            if (seenWords.get(word)! > wordCount.get(word)!) break;
        }
        
        // 모든 단어를 올바르게 찾았다면 시작 인덱스를 결과에 추가
        if (j === words.length) {
            result.push(i);
        }
    }
    
    return result;
}