[LeetCode] 127. Word Ladder

轉自LeetCode

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.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

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.

<Solution>

這題是很典型的 BFS 題目

code 如下
c++

	class Solution {
	public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
	queue<pair<string, int>> wordQue;
	wordQue.push({beginWord, 1});
	vector<bool> isUsed(wordList.size(), false);
	//>> use BFS
	while(!wordQue.empty()) {
	const string tmpStr = wordQue.front().first;
	const int step = wordQue.front().second;
	if (endWord.compare(tmpStr) == 0) {
	return step;
	}
	for (int i = 0; i < isUsed.size(); i++) {
	if (!isUsed[i] && diffCnt(tmpStr, wordList[i]) == 1) {
	wordQue.push({wordList[i], step+1});
	isUsed[i] = true;
	}
	}
	wordQue.pop();
	}
	return 0;
	}
	int diffCnt(const string &str1, const string &str2) {
	int cnt = 0;
	for(int i = 0; i < str1.length(); i++) {
	if(str1[i] != str2[i]) {
	++cnt;
	if(cnt > 1) {
	return cnt;
	}
	}
	}
	return cnt;
	}
	};

view raw wordLadder_1.cpp hosted with ❤ by GitHub

上面這個解法會過，但是時間會比較久 可以利用 hash map 來做一些加速

思路如下

• 一樣使用到 BFS 的概念，但先把 wordList 轉換成 unordered_set，來加速判斷 word 是否在 list 裡

• 一樣使用一個 queue 來記錄該 word，以及到達該 word 的所需步數

• 對於每個 word 的每個位置，都做字母 a 到 z 的變化，來組成新的 word

• 看看新的 word 是否就是答案

• 如果不是答案，利用步驟一所產生的 hash map 來看新的word，是否存在 wordList 裡面。如果存在，就放到 queue 裡，預備做下一次檢查

code 如下(參考資料)
c++

	class Solution {
	public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
	//>> transform wordList to hash map
	unordered_set<string> wordSet;
	for(const auto &w : wordList) {
	wordSet.insert(w);
	}
	//>> check endWord is valid
	if(wordSet.find(endWord) == wordSet.end()) {
	return 0;
	}
	queue<pair<string, int>> wordQue;
	wordQue.push({beginWord, 1});
	const int len = beginWord.length();
	while(!wordQue.empty()) {
	const string word = wordQue.front().first;
	const int step = wordQue.front().second;
	for(int i = 0; i < len; i++) {
	string newWord = word;
	for(char ch = 'a'; ch <= 'z'; ch++) {
	newWord[i] = ch;
	//>> find ans
	if(endWord.compare(newWord) == 0) {
	return step+1;
	}
	//>> newWord is a valid next move
	if(wordSet.find(newWord) != wordSet.end()) {
	wordQue.push({newWord, step+1});
	wordSet.erase(newWord);
	}
	}
	}
	wordQue.pop();
	}
	return 0;
	}
	};

view raw wordLadder_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
	val wordSet = wordList.toMutableSet()
	if(!wordSet.contains(endWord)) {
	return 0
	}
	val map = mutableMapOf<String,Int>()
	val queue = mutableListOf(beginWord)
	map[beginWord] = 1
	while(queue.isNotEmpty()) {
	val word = queue.first()
	queue.removeAt(0)
	for(i in word.indices) {
	var newWord = word.toCharArray()
	for(c in 'a'..'z') {
	newWord[i] = c
	val newString = newWord.joinToString("")
	if(wordSet.contains(newString)) {
	if(newString == endWord) {
	return map[word]!! + 1
	} else if(map[newString] == null) {
	queue.add(newString)
	map[newString] = map[word]!! + 1
	}
	}
	}
	}
	}
	return 0
	}
	}

view raw word_ladder.kt hosted with ❤ by GitHub

還有一個進化版的BFS解法

依然使用 hash map 來加速，但是這次改從兩端同時找起

核心想法是，如果能從 beginWord 變化到 endWord，那麼也能從 endWord 變化到 beginWord

其餘思路如下

• 準備兩個 set，以及兩個指標，分別指到 size 比較小的 set 和 size 比較大的 set

• 要區分大小 set 的原因也是用來加速，每次都只歷遍比較小的 set 去找答案

• 如果在比較小的 set 中的 word，可以變一個字就變成在比較大的 set 中的 word，這樣就代表找到答案了。因為兩個 set 分別從兩端來找，當一個 set 裡面的 word 可以變化成另外一個 set 裡面的 word 的時候，就是相遇點，代表可以把兩端給串起來

• 如果不在另一個 set 裡面，那就檢查變化後的 word 是否可用，可用的話就放到 nextReachableSet，最後在和 smallerSet 做 swap，用來進行下次的檢查

code 如下(參考資料)

	class Solution {
	public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
	//>> transform wordList to hash map
	unordered_set<string> wordSet;
	for(const auto &w : wordList) {
	wordSet.insert(w);
	}
	//>> prepare two sets. one is from head and the other is from end
	unordered_set<string> headSet, tailSet, *smallerSetPtr, *biggerSetPtr;
	headSet.insert(beginWord);
	//>> check endWord is valid or not
	if(wordSet.find(endWord) == wordSet.end()) {
	return 0;
	}
	else {
	tailSet.insert(endWord);
	wordSet.erase(endWord);
	}
	int step = 1;
	const int len = beginWord.length();
	while(!headSet.empty() && !tailSet.empty()) {
	++step;
	smallerSetPtr = (headSet.size() < tailSet.size()) ? &headSet : &tailSet;
	biggerSetPtr = (headSet.size() < tailSet.size()) ? &tailSet : &headSet;
	unordered_set<string> nextReachableSet;
	for(const auto &word : *smallerSetPtr) {
	for(int i = 0; i < len; i++) {
	string newWord = word;
	for(char ch = 'a'; ch <= 'z'; ch++) {
	newWord[i] = ch;
	//>> find ans
	if(biggerSetPtr->find(newWord) != biggerSetPtr->end()) {
	return step;
	}
	//>> find next valid word
	if(wordSet.find(newWord) != wordSet.end()) {
	nextReachableSet.insert(newWord);
	wordSet.erase(newWord); //>> mark newWord is used
	}
	}
	}
	}
	//>> chang smallerSet to nextReachableSet
	*smallerSetPtr = nextReachableSet;
	}
	return 0;
	}
	};

view raw wordLadder_3.cpp hosted with ❤ by GitHub