Medium

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.

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

## Analysis

StringBuilder()

``````StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(j, ch);
String newWord = sb.toString();
...
}``````

toCharArray()

``````char[] chs = s.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++ ) {
chs[i] = ch;
String newStr = new String(chs);
...
}``````

### The intuition:

BFS -- Altering one character at a time for beginWord, and see if it's in the wordList, if yes, then add to the `toSearch` list; for the word in `toSearch` list, do the same: altering one character at a time, see if it's in wordList, so on and so forth.

Note: to avoid cyclical search, we need to remove the "searched" word from the wordList

Optimization: using two end BFS

## Solution

### BFS (using set)- (133ms 43.15%)

``````class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// wordSet storing non-visited words
Set<String> wordSet = new HashSet<String> (wordList);
// reachSet storing visted words
Set<String> reachSet = new HashSet<String>();
if (beginWord == null || endWord == null || !wordSet.contains(endWord)) return 0;

int step = 1;

while (!reachSet.contains(endWord)) {
HashSet<String> temp = new HashSet<String>();
for (String s : reachSet) {
for (int i = 0; i < s.length(); i++) {
char[] chs = s.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++ ) {
chs[i] = ch;
String nStr = new String(chs);
if (wordSet.contains(nStr)) {
if (endWord.equals(nStr)) return step + 1;
// add new valid word to the temp set
wordSet.remove(nStr);
}
}
}
}
step++;
if (temp.size() == 0) return 0;
reachSet = temp;
}
return step;
}
}``````

### A more "traditional" BFS using Queue (63 ms, faster than 78.37%)

``````class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) {
return 0;
}

Deque<String> q = new ArrayDeque<>();
q.offer(beginWord);
int step = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String word = q.poll();
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(j, ch);
String newWord = sb.toString();
if (newWord.equals(endWord)) {
return step + 1;
}
if (set.contains(newWord)) {
q.offer(newWord);
set.remove(newWord); // to avoid infinited loop
}
}
}
}
step++;
}
return 0;
}
}``````

### Two-End BFS (15 ms, faster than 99.01%)

``````class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>();

if (beginWord == null || endWord == null || !set.contains(endWord)) return 0;

Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
set.remove(endWord);
int step = 1;

while(!beginSet.isEmpty() && !endSet.isEmpty()) {
Set<String> next = new HashSet<>();
if (beginSet.size() > endSet.size()) {
Set<String> temp = beginSet;
beginSet = endSet;
endSet = temp;
}

for(String str : beginSet) {
char[] word = str.toCharArray();
for(int i = 0; i < word.length; i++) {
char old_c = word[i];

for(char c = 'a'; c <= 'z'; c++) {
word[i] = c;
String cur = new String(word);
if (endSet.contains(cur)) return step+1;
if (set.contains(cur)) {
set.remove(cur);
}
}
word[i] = old_c;
}
}
beginSet = next;
step++;
}
return 0;
}
}``````