Created
June 11, 2022 21:03
-
-
Save ali-alaei/0fe6fc081bd610cc0a75d721e5195edd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
Map<String, List<String>> adjList = new HashMap<String, List<String>>(); | |
List<String> currPath = new ArrayList<String>(); | |
List<List<String>> shortestPaths = new ArrayList<List<String>>(); | |
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { | |
// copying the words into the set for efficient deletion in BFS | |
Set<String> copiedWordList = new HashSet<>(wordList); | |
// build the graph using BFS | |
bfs(beginWord, endWord, copiedWordList); | |
// every path will start from the beginWord | |
currPath.add(beginWord); | |
// traverse the graph to find all the paths between beginWord and | |
endWord | |
backtrack(beginWord, endWord); | |
return shortestPaths; | |
} | |
private List<String> findNeighbors(String word, Set<String> wordList) { | |
List<String> neighbors = new ArrayList<String>(); | |
char charList[] = word.toCharArray(); | |
for (int i = 0; i < word.length(); i++) { | |
char oldChar = charList[i]; | |
// replace the i-th character with all letters from a to z | |
except the original character | |
for (char c = 'a'; c <= 'z'; c++) { | |
charList[i] = c; | |
// skip if the character is same as original or if the word | |
is not present in the wordList | |
if (c == oldChar || !wordList.contains(String.valueOf(charList))) { | |
continue; | |
} | |
neighbors.add(String.valueOf(charList)); | |
} | |
charList[i] = oldChar; | |
} | |
return neighbors; | |
} | |
private void backtrack(String source, String destination) { | |
// store the path if we reached the endWord | |
if (source.equals(destination)) { | |
List<String> tempPath = new ArrayList<String>(currPath); | |
shortestPaths.add(tempPath); | |
} | |
if (!adjList.containsKey(source)) { | |
return; | |
} | |
for (int i = 0; i < adjList.get(source).size(); i++) { | |
currPath.add(adjList.get(source).get(i)); | |
backtrack(adjList.get(source).get(i), destination); | |
currPath.remove(currPath.size() - 1); | |
} | |
} | |
private void bfs(String beginWord, String endWord, Set<String> wordList) { | |
Queue<String> q = new LinkedList<>(); | |
q.add(beginWord); | |
// remove the root word which is the first layer in the BFS | |
if (wordList.contains(beginWord)) { | |
wordList.remove(beginWord); | |
} | |
Map<String, Integer> isEnqueued = new HashMap<String, Integer>(); | |
isEnqueued.put(beginWord, 1); | |
while (q.size() > 0) { | |
// visited will store the words of current layer | |
List<String> visited = new ArrayList<String>(); | |
for (int i = q.size() - 1; i >= 0; i--) { | |
String currWord = q.peek(); | |
q.remove(); | |
// findNeighbors will have the adjacent words of the | |
currWord | |
List<String> neighbors = findNeighbors(currWord, wordList); | |
for (String word : neighbors) { | |
visited.add(word); | |
if (!adjList.containsKey(currWord)) { | |
adjList.put(currWord, new ArrayList<String>()); | |
} | |
// add the edge from currWord to word | |
in the list | |
adjList.get(currWord).add(word); | |
if (!isEnqueued.containsKey(word)) { | |
q.add(word); | |
isEnqueued.put(word, 1); | |
} | |
} | |
} | |
// removing the words of the previous layer | |
for (int i = 0; i < visited.size(); i++) { | |
if (wordList.contains(visited.get(i))) { | |
wordList.remove(visited.get(i)); | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment