Skip to content

Instantly share code, notes, and snippets.

@hsaputra
Created August 16, 2020 06:13
Show Gist options
  • Save hsaputra/106aa5ca968ba1c03e4c1520578414b9 to your computer and use it in GitHub Desktop.
Save hsaputra/106aa5ca968ba1c03e4c1520578414b9 to your computer and use it in GitHub Desktop.
Word ladder
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// check input
if (!wordList.contains(endWord)) {
return 0;
}
// We are going to use BFS to build the graph of the beginWord to endWord using
// all words in the wordList
Queue<String> levelBFS = new LinkedList();
// The Queue is used to manage per level of the BFS
Set<String> hasSeenWord = new HashSet();
int level = 0;
// add beginWord to start
levelBFS.add(beginWord);
hasSeenWord.add(beginWord);
while (!levelBFS.isEmpty()) {
final int levelCount = levelBFS.size();
++level;
//System.out.println("Process level: " + level);
// iterate current BFS level
for (int i = 0; i < levelCount; i++) {
String cur = levelBFS.poll();
cur = cur.toLowerCase();
final char[] curCharArray = cur.toCharArray();
for (int pos = 0; pos < curCharArray.length; pos++) {
final char originalChar = curCharArray[pos];
// Replace each letter with a-z and check if it is in the word list,
// if it does check if it match, if not match simply add to Queue
for (char r = 'a'; r <= 'z'; r++) {
curCharArray[pos] = r;
// check if it is a match
String variance = new String(curCharArray);
if (variance.equals(endWord)) {
// got match, return level
//System.out.println("Found at level: " + level);
return level + 1;
} else {
// else check in wordList, if yes and not in seen set, add it to
// queue
if (wordList.contains(variance) && !hasSeenWord.contains(variance)) {
//System.out.println("Add to BFS queue : " + variance);
hasSeenWord.add(variance);
levelBFS.add(variance);
} else {
//System.out.println("Not added word : " + variance);
}
}
}
// restore char
curCharArray[pos] = originalChar;
}
}
}
return 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment