https://leetcode.com/problems/word-ladder/
Breadth First Search, Using HashMap to achieve O(1) searching, compared with O(n) searching of List1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int L=beginWord.length();
Map<String,List<String>> map=new HashMap<>();
wordList.forEach(word->{
for(int i=0;i<L;i++){
String newStr=word.substring(0,i)+"*"+word.substring(i+1,L);
List<String> ls=map.getOrDefault(newStr,new ArrayList<>());
ls.add(word);
map.put(newStr,ls);
}
});
Map<String,Boolean> seen=new HashMap<>();
Queue<String> q=new LinkedList<>();
int level=1;
q.offer(beginWord);
while(!q.isEmpty()){
int qSize=q.size();
while(qSize>0){
String str=q.poll();
for(int i=0;i<L;i++){
String tmpStr=str.substring(0,i)+"*"+str.substring(i+1,L);
for(String s:map.getOrDefault(tmpStr,new ArrayList<>())){
if(seen.getOrDefault(s,false)) continue;
if(s.equals(endWord)) return level+1;
q.add(s);
seen.put(s,true);
}
}
qSize--;
}
level++;
}
return 0;
}
}
/*
public class MyClass {
public static void main(String[] args) {
String beginWord = "hit";
String endWord = "cog";
List<String> wordList = new ArrayList<>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
System.out.println(new Solution().ladderLength(beginWord, endWord, wordList));
}
}*/
Bidirectional Breadth First Search1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77class Pair<K, V>{ /*implements interfacePair<K, V>*/
public K key;
public V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {return key;}
public V getValue() {return value;}
}
class Solution {
private int L;
private Map<String, List<String>> allComboDict;
Solution() {
this.L = 0;
this.allComboDict = new HashMap<>();
}
private int visitWordNode(Queue<Pair<String, Integer>> Q, Map<String, Integer> visited, Map<String, Integer> othersVisited) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < this.L; i++) {
// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
// Next states are all the words which share the same intermediate state.
for (String adjacentWord : this.allComboDict.getOrDefault(newWord, new ArrayList<>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
if (othersVisited.containsKey(adjacentWord)) {
return level + othersVisited.get(adjacentWord);
}
if (!visited.containsKey(adjacentWord)) {
// Save the level as the value of the dictionary, to save number of hops.
visited.put(adjacentWord, level + 1);
Q.add(new Pair<String, Integer>(adjacentWord, level + 1));
}
}
}
return -1;
}
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) return 0;
this.L = beginWord.length();
wordList.forEach(word -> {
for (int i = 0; i < L; i++) {
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations = this.allComboDict.getOrDefault(newWord, new ArrayList<>());
transformations.add(word);
this.allComboDict.put(newWord, transformations);
}
});
Queue<Pair<String, Integer>> Q_begin = new LinkedList<>();
Queue<Pair<String, Integer>> Q_end = new LinkedList<>();
Q_begin.add(new Pair<String, Integer>(beginWord, 1));
Q_end.add(new Pair<String, Integer>(endWord, 1));
Map<String, Integer> visitedBegin = new HashMap<>();
Map<String, Integer> visitedEnd = new HashMap<>();
visitedBegin.put(beginWord, 1);
visitedEnd.put(endWord, 1);
while (!Q_begin.isEmpty() && !Q_end.isEmpty()) {
// One hop from begin word
int ans = visitWordNode(Q_begin, visitedBegin, visitedEnd);
if (ans > -1) return ans;
// One hop from end word
ans = visitWordNode(Q_end, visitedEnd, visitedBegin);
if (ans > -1) return ans;
}
return 0;
}
}