[Leetcode Top Interview 150] 127. Word Ladder

난이도 : hard

문제링크

• 두개의 문자열이 주어진다 : beginWord, endWord
• 한개의 문자열 리스트가 주어진다 : wordList
• 이웃한 한 단어 차이만 나는 단어의 쌍들끼리 변환될 수 있다
• beginWord에서 endWord로 변환할 때, 가장 적은 수의 변환의 수를 리턴하라

 

1. 접근법

• 최소 변환수를 구해야 하므로 큐를 사용하여 BFS 탐색으로 모든 경우를 탐색한다
• 큐에서 꺼낸 단어와 한글자 차이나는 단어들을 큐에 넣고, 큐가 빌때까지 반복한다
• 한번 탐색한 단어는 다시 탐색하지 않도록 방문단어들을 Set에 저장해둔다

 

3. 구현 코드

class Node {
    String word;
    int turn;

    Node (String word, int turn) {
        this.word = word;
        this.turn = turn;
    }
}

Set<String> visited;
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    int size = wordList.size();
    visited = new HashSet<>(size);
    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node(beginWord, 1));

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        String word = node.word;
        int turn = node.turn;

        if (word.equals(endWord)) {
            return turn;
        }

        for (String next : wordList) {
            if (isOneDiscrepency(word, next) && !visited.contains(next)) {
                visited.add(next);
                queue.offer(new Node(next, turn+1));
            }
        }
    }

    return 0;
}

private boolean isOneDiscrepency(String word, String next) {
    int count = 0;
    for (int i = 0; i < word.length(); i++) {
        if (word.charAt(i) != next.charAt(i)) count++;
        if (count > 1) return false;
    }

    return true;
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 단어 탐색
• 공간복잡도 : O(n) - 단어 방문시 단어를 Set에 저장함