## ้ข็ฎๆ่ฟฐ

``````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:

Only one letter can be changed at a time.
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 #1 BFS

1> ่ทๅ้ปๆฅ่กจ

2> ้็จBFS Queue> queue๏ผ ๆๅ่ฟๅlevel + 1

Complexity Analysis

• Time Complexity: O(MรN), where M is the length of words and N is the total number of words in the input word list. Finding out all the transformations takes M iterations for each of the N words. Also, breadth first search in the worst case might go to each of the N words.

• Space Complexity: O(MรN), to store all M transformations for each of the N words, in the `all_combo_dict` dictionary. Visited dictionary is of N size. Queue for BFS in worst case would need space for all N words.

``````class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int L = beginWord.length();
// map: a*c = > abc
Map<String, List<String>> allComboDict = new HashMap<>();
wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
allComboDict.putIfAbsent(newWord, new ArrayList());
}
});

HashSet<String> visited = new HashSet<String>();

Queue<Pair<String, Integer>> queue = new LinkedList<>();
while (!queue.isEmpty()) {
Pair<String, Integer> node = queue.poll();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
return level + 1;
}

}
}
}
}

return 0;
}
}``````

### Approach #2 BFS

``````class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (wordList == null) return 0;
if (beginWord.equals(endWord)) return 1;

HashSet<String> dict = new HashSet<String>(wordList);

HashSet<String> visit = new HashSet<String>();
queue.offer(beginWord);

int transformation = 1;
while (!queue.isEmpty()) {
transformation++;
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
for (String nextWord : getNextWords(word, dict)) {
if (visit.contains(nextWord)) {
continue;
}
if (nextWord.equals(endWord)) {
return transformation;
}

queue.offer(nextWord);
}
}
}
return 0;
}

private ArrayList<String> getNextWords(String word, Set<String> dict) {
ArrayList<String> nextWords = new ArrayList<String>();
for (char c = 'a'; c <= 'z'; c++) {
for (int i = 0; i < word.length(); i++) {
if (c == word.charAt(i)) {
continue;
}
String nextWord = replace(word, i, c);
if (dict.contains(nextWord)) {
}
}
}
return nextWords;
}

private String replace(String s, int index, char c) {
char[] chars = s.toCharArray();
chars[index] = c;
return new String(chars);
}

}``````

Last updated