[LeetCode] 127. Word Ladder

😎풀이

BFS를 활용하여 간단한 풀이가 가능하다.

주요 로직은 다음과 같다.

1. endWord가 wordList에 있는지 우선 검증 (없다면 당연히 생성 불가)
2. 단어의 각 자리를 a-z 까지 변경해보며 wordList 내에 있는 단어이며 아직 생성해보지 않았다면 queue에 추가
3. endWord와 갖게 변형된다면 해당 level 반환
4. 못 변형한다면 0 반환

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    // wordList를 Set으로 변환하여 O(1) 시간에 단어 존재 여부를 확인할 수 있게 함
    const wordSet = new Set(wordList);
    
    // endWord가 wordList에 없으면 변환이 불가능하므로 0 반환
    if (!wordSet.has(endWord)) return 0;
    
    // BFS를 위한 큐 초기화
    // [단어, 지금까지의 변환 횟수]를 저장
    const queue: [string, number][] = [[beginWord, 1]];
    
    // 이미 방문한 단어를 저장하는 Set
    const visited = new Set<string>();
    visited.add(beginWord);
    
    while (queue.length > 0) {
        const [currentWord, level] = queue.shift()!;
        
        // 현재 단어의 각 위치를 a-z로 변경해보며 가능한 다음 단어들을 찾음
        for (let i = 0; i < currentWord.length; i++) {
            for (let c = 97; c <= 122; c++) { // 'a'(97)부터 'z'(122)까지
                const newWord = 
                    currentWord.slice(0, i) + 
                    String.fromCharCode(c) + 
                    currentWord.slice(i + 1);
                
                // endWord를 찾으면 현재까지의 레벨 + 1을 반환
                if (newWord === endWord) {
                    return level + 1;
                }
                
                // 새로운 단어가 wordSet에 있고 아직 방문하지 않았다면 큐에 추가
                if (wordSet.has(newWord) && !visited.has(newWord)) {
                    visited.add(newWord);
                    queue.push([newWord, level + 1]);
                }
            }
        }
    }
    
    // 변환 sequence를 찾지 못한 경우 0 반환
    return 0;
}