Medium
卧槽，我真的强烈地感觉这道题是DFS呀，结果看答案都是BFS做的，趁机好好反省一下，最近的一次刷这道题仅仅是在一个月前，就连基本的处理方向都选错了。
我有句妈卖批不知当讲不当讲，这道题一直TLE搞了一个多小时，然后我发现一个discussion里的帖子说把给的wordList从List换成Set就好了，卧槽我换了之后果然好了，害我以为implement的细节哪里有问题。好吧，set的查询是O(1) List是O(N), 确实应该敏感地换掉
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)){
return 0;
}
int steps = 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
while (!queue.isEmpty()){
steps++;
int size = queue.size();
for (int i = 0; i < size; i++){
String word = queue.poll();
if (word.equals(endWord)){
return steps;
}
for (int j = 0; j < word.length(); j++){
char[] chars = word.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++){
if(chars[j] == ch){
continue;
}
chars[j] = ch;
String newWord = String.valueOf(chars);
if (dict.contains(newWord) && !visited.contains(newWord)){
queue.offer(newWord);
visited.add(newWord);
}
}
}
}
}
return 0;
}
}
