[LeetCode] 140. Word Break II

😎풀이

해당 문제를 풀고 보니 가장 효율성 있는 코드를 작성하신 분이 대단함을 느꼈음

풀이 절차는 다음과 같다.

1. backTracking 함수에서 전달받은 인자를 통해 시작점을 파악함
2. 시작점에서 1씩 증가하는 반복문을 통해 문자열을 잘라내어 해당 단어가 사전에 있는지 파악한다.
3. backTracking함수를 재귀적으로 호출하여 잘라낸 문자열을 통해 만들어 낼 수 있는 문장을 확인한다.
4. 현재 문자와 확인된 문장을 공백을 통해 연결한다.

function wordBreak(s: string, wordDict: string[]): string[] {
    // 결과를 저장할 배열
    const result: string[] = [];
    
    // 단어 사전을 Set으로 변환하여 검색 속도 향상
    const dict: Set<string> = new Set(wordDict);
    
    // 메모이제이션을 위한 Map
    // key: 시작 인덱스, value: 해당 인덱스에서 시작하는 가능한 모든 문장
    const memo: Map<number, string[]> = new Map();
    
    // 재귀적으로 문자열을 분해하는 함수
    function backtrack(start: number): string[] {
        // 이미 계산된 결과가 있다면 반환
        if (memo.has(start)) {
            return memo.get(start)!;
        }
        
        // 현재 위치에서 가능한 모든 문장을 저장할 배열
        const sentences: string[] = [];
        
        // 문자열 끝에 도달한 경우
        if (start === s.length) {
            // 백 트레킹 이후 for문을 접근하기 위한 빈 문자열
            sentences.push("");
            return sentences;
        }
        
        // 현재 위치에서 시작하여 모든 가능한 단어를 찾음
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.slice(start, end);
            
            // 현재 단어가 사전에 있는 경우
            if (!dict.has(word)) continue
            // 나머지 문자열에 대해 재귀적으로 해결
            const subSentences = backtrack(end);
            
            // 현재 단어와 나머지 문장들을 조합
            for (const subSentence of subSentences) {
                sentences.push(
                    // 빈 문자열이 입력되었다면, 탐색이 종료되었다는 뜻으로 현재 word만 입력
                    subSentence.length === 0 
                        ? word 
                        : `${word} ${subSentence}`
                );
            }
        }
        
        // 결과를 메모이제이션
        memo.set(start, sentences);
        return sentences;
    }
    
    // 시작 위치 0부터 시작
    return backtrack(0);
}