[LeetCode] Word Ladder

문제

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Example 2:

Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

 

Approach

BFS를 사용한다.

초기에 beginWord를 큐에 넣고 BFS를 돌리며 wordList의 단어들 중 한 글자만 다른 글자,

즉 변환 가능한 글자를 찾아 큐에 넣는다.

https://noname122.tistory.com/64 이 문제를 풀 때 처럼 level도 알아야 하기 때문에 따로 신경써준다.

 

Optimize

변환 가능한 글자를 찾는걸 따로 함수를 만들어서 했었는데

여기서 오버헤드가 굉장히 컸다.

이렇게 안하고 wordList를 set에 옮기고

q.front()에서 뽑은 단어를 자리마다 한 글자씩 바꿔가며 set에서 find하는 방식으로

변환 가능한 글자를 찾으니 확 빨라졌다. (단 set.find() 말고 find(set.begin(), set.end(), word)는 타임오버)

 

Code

Slow: https://github.com/chi3236/algorithm/blob/master/LeetCode_WordLadder_slow.cpp

Optimized: https://github.com/chi3236/algorithm/blob/master/LeetCode_WordLadder_optimized.cpp