leetcode 127) Word Ladder

LV. Hard 🥵

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

Word Ladder - LeetCode

 

문제

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

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

 

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

 

문제 해결법

처음 단어부터 시작해서 이동할 수 있는 단어를 큐에 넣어주고 큐에 아무것도 없을 때까지 확인해주면 끝!

 

해결 코드

class Solution {
private:
	int ans;
public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		queue<string> q;
		vector<bool> check(wordList.size(), false);

		// wordlist에 endWord가 없을 때
		if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())
			return 0;

		ans = 1;
		q.push(beginWord);
		while (!q.empty()) {
			int size = q.size();
			for (int i = 0; i < size; ++i) {
				string word = q.front();
				q.pop();
				if (word == endWord)
					return ans;
				for (int j = 0; j < wordList.size(); ++j) {
					if (!check[j] && checkWordCanChange(word, wordList[j])) {
						check[j] = true;
						q.push(wordList[j]);
					}
				}
			}
			ans++;
		}
		return 0;
	}
	bool checkWordCanChange(string origin_word, string new_word) {
		int count = 0;
		for (int i = 0; i < origin_word.length(); ++i) {
			if (origin_word[i] != new_word[i])
				count++;
		}
		return count == 1;
	}
};