[Leetcode] 127. Word Ladder

문제 : https://leetcode.com/problems/word-ladder/

---

문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환시퀀스 길이를 구하라. 만일 변환 불가능하다면 0을 반환하라.

---

126. Word Ladder2 와 비슷하게 풀었다. 126번과 이번문제와의 차이점은 반환값이 변환시퀀스 리스트인지, 변환시퀀스 길이인지이다.

 

ex)

// input
beginWord = "hit", endWord = "cog", wordList = ["hit", "hot","dot","dog","lot","log","cog"]

 

126번 문제와 비슷하게 BFS로 풀고, 이를 위해 먼저 그래프 구조를 만든다.

정점은 wordList 문자열들이고 간선은 wordList의 문자열들을 한 문자씩 변경해가며 변경가능한 문자열들을 연결한다.

위 예시를 위 방법대로 연결한다면 아래와 같이 연결된다.

cog -> log, dog 
log -> cog, lot, dog 
dog -> cog, log, dot 
dot -> dog, lot, hot 
hit -> hot 
lot -> log, hot, dot 
hot -> lot, dot, hit

 

그래프를 만들었으니 bfs를 돌린다.

큐에 문자열과 해당 문자열을 만들기 위해 beginWord부터의 시퀀스 길이와 문자열을 저장한다. 

예를 들어 처음 큐에는 {1, "hit"}이 저장된다.

위에서 만든 그래프에서 탐색중인 문자열에 해당하는 정점에 연결된 간선들을 탐색한다.

또한 문자열은 중복해서 방문하면 안되므로 set에 따로 저장하며 중복 방문을 방지한다.

hit -> hot ({2, "hot"})

 

hit -> hot -> lot ({3, "lot"})
           -> dot  ({3, "dot"})

hit -> hot -> lot -> log ({4, "log"})
           -> dot -> dog  ({4, "dog"})

hit -> hot -> lot -> log -> cog ({5, "cog"})
           -> dot -> dog -> cog ({5, "cog"})

bfs로 탐색하며 큐에는 위와 같은 데이터들이 갱신되며 예시의 정답은 5가 된다.

 

시간복잡도는 N = |wordList|라 했을 때, O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/127.%20Word%20Ladder.cpp