Question 2 Word Ladder I
Method 1 DFS backtracking
Method 2 BFS
High level
this is a graph problem,
vertex:每个单词就是一个点
edge:在wordList里面和自己只相差一个字典的单词都是neighbor
therefore, this problem is asking about the shortest path problem
from start node to target node
unit weight shortest path problem
method BFS
High level of BFS
Expansion: 每一次我从Queue里poll处当前层需要expand(visit)的node
Generation:得有办法找到wordList里所有和当前层expand的word相差一个字的
Details
generation这一步怎么做?
Method 1: Brute Force
// Some code
public List<String> getAllTheNeighborWords(String cur, Set<String> wordList) {
List<String> result = new ArrayList<>();
for (String word: wordList) {
if (isNei(word, cur)) {
result.add(word);
}
}
return result;
}
private boolean isNei(String cur, String word) {
if (word.length() != cur.length) {
return false;
}
int count = 0;
for (int i = 0; i < cur.length(); i++) {
if (cur.charAt(i) != word.charAt(i)) {
count++;
if(count > 1) {
return false;
}
}
}
return true;
}
Method 2 自己探索隐藏的图
直接从单词本身出发==》 从Node本身出发去找neighbor
遍历这个单词,尝试替换每个单词中的每个字母,看看这个单词在不在wordList里面
// Some code
public List<String> getAllTheNeighborWords(String cur; List<String> wordList) {
List<String> result = new ArrayList<>();
char[] array = cur.toCharArray();
for (int i = 0; i < array.length; i++) {
char temp = array[i];
for (char j = 'a' ; j <= 'z'; j++) {
if (temp != j) {
array[i] = j;
String newWord = new String(array);
if (wordList.contains(newWorld)) {
result.add(newWorld);
}
array[i] = temp; //一定要换回
}
}
// array[i] = temp; // better
}
return result;
}
// Some code
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet= new HashSet<>();
for (String word: wordList) {
wordSet.add(s);
}
Deque<String> queue = new ArrayDeque<>(0l
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
List<String> allNeighbors = getAllTheNeightborWords(cur, wordSet);
if (!allNeighbors.isEmpty()) {
for (String nei: allNeighbors) {
if (nei.equals(endWord)) {
return level + 1;
}
if (!visited.contains(nei)) {
queue.offer(nei);
visited.add(nei);
}
}
}
}
level++;
}
return 0;
}
Clarification && Assumption:
StartWord 和 EndWord一样怎么办
EndWord or StartWord 不在wordList里怎么办
到不了return什么?
Modeling Graph
Last updated