forked from gouthampradhan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
WordLadderII.java
130 lines (121 loc) · 8.4 KB
/
WordLadderII.java
1
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package breadth_first_search;
import java.util.*;
/**
* Created by gouthamvidyapradhan on 24/03/2017.
* Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
* <p>
* Only one letter can be changed at a time
* Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
* For example,
* <p>
* Given:
* beginWord = "hit"
* endWord = "cog"
* wordList = ["hot","dot","dog","lot","log","cog"]
* Return
* [
* ["hit","hot","dot","dog","cog"],
* ["hit","hot","lot","log","cog"]
* ]
* Note:
* Return an empty list 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.
*/
public class WordLadderII {
private static Queue<String> queue = new ArrayDeque<>();
private static Set<String> dictionary = new HashSet<>();
private static final String CONST = "abcdefghijklmnopqrstuvwxyz";
private static Map<String, Set<String>> graph = new HashMap<>();
private static Map<String, Integer> minDistance = new HashMap<>();
private static List<List<String>> result = new ArrayList<>();
/**
* Main method
*
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
List<String> dic = Arrays.asList("kid", "tag", "pup", "ail", "tun", "woo", "erg", "luz", "brr", "gay", "sip", "kay", "per", "val", "mes", "ohs", "now", "boa", "cet", "pal", "bar", "die", "war", "hay", "eco", "pub", "lob", "rue", "fry", "lit", "rex", "jan", "cot", "bid", "ali", "pay", "col", "gum", "ger", "row", "won", "dan", "rum", "fad", "tut", "sag", "yip", "sui", "ark", "has", "zip", "fez", "own", "ump", "dis", "ads", "max", "jaw", "out", "btu", "ana", "gap", "cry", "led", "abe", "box", "ore", "pig", "fie", "toy", "fat", "cal", "lie", "noh", "sew", "ono", "tam", "flu", "mgm", "ply", "awe", "pry", "tit", "tie", "yet", "too", "tax", "jim", "san", "pan", "map", "ski", "ova", "wed", "non", "wac", "nut", "why", "bye", "lye", "oct", "old", "fin", "feb", "chi", "sap", "owl", "log", "tod", "dot", "bow", "fob", "for", "joe", "ivy", "fan", "age", "fax", "hip", "jib", "mel", "hus", "sob", "ifs", "tab", "ara", "dab", "jag", "jar", "arm", "lot", "tom", "sax", "tex", "yum", "pei", "wen", "wry", "ire", "irk", "far", "mew", "wit", "doe", "gas", "rte", "ian", "pot", "ask", "wag", "hag", "amy", "nag", "ron", "soy", "gin", "don", "tug", "fay", "vic", "boo", "nam", "ave", "buy", "sop", "but", "orb", "fen", "paw", "his", "sub", "bob", "yea", "oft", "inn", "rod", "yam", "pew", "web", "hod", "hun", "gyp", "wei", "wis", "rob", "gad", "pie", "mon", "dog", "bib", "rub", "ere", "dig", "era", "cat", "fox", "bee", "mod", "day", "apr", "vie", "nev", "jam", "pam", "new", "aye", "ani", "and", "ibm", "yap", "can", "pyx", "tar", "kin", "fog", "hum", "pip", "cup", "dye", "lyx", "jog", "nun", "par", "wan", "fey", "bus", "oak", "bad", "ats", "set", "qom", "vat", "eat", "pus", "rev", "axe", "ion", "six", "ila", "lao", "mom", "mas", "pro", "few", "opt", "poe", "art", "ash", "oar", "cap", "lop", "may", "shy", "rid", "bat", "sum", "rim", "fee", "bmw", "sky", "maj", "hue", "thy", "ava", "rap", "den", "fla", "auk", "cox", "ibo", "hey", "saw", "vim", "sec", "ltd", "you", "its", "tat", "dew", "eva", "tog", "ram", "let", "see", "zit", "maw", "nix", "ate", "gig", "rep", "owe", "ind", "hog", "eve", "sam", "zoo", "any", "dow", "cod", "bed", "vet", "ham", "sis", "hex", "via", "fir", "nod", "mao", "aug", "mum", "hoe", "bah", "hal", "keg", "hew", "zed", "tow", "gog", "ass", "dem", "who", "bet", "gos", "son", "ear", "spy", "kit", "boy", "due", "sen", "oaf", "mix", "hep", "fur", "ada", "bin", "nil", "mia", "ewe", "hit", "fix", "sad", "rib", "eye", "hop", "haw", "wax", "mid", "tad", "ken", "wad", "rye", "pap", "bog", "gut", "ito", "woe", "our", "ado", "sin", "mad", "ray", "hon", "roy", "dip", "hen", "iva", "lug", "asp", "hui", "yak", "bay", "poi", "yep", "bun", "try", "lad", "elm", "nat", "wyo", "gym", "dug", "toe", "dee", "wig", "sly", "rip", "geo", "cog", "pas", "zen", "odd", "nan", "lay", "pod", "fit", "hem", "joy", "bum", "rio", "yon", "dec", "leg", "put", "sue", "dim", "pet", "yaw", "nub", "bit", "bur", "sid", "sun", "oil", "red", "doc", "moe", "caw", "eel", "dix", "cub", "end", "gem", "off", "yew", "hug", "pop", "tub", "sgt", "lid", "pun", "ton", "sol", "din", "yup", "jab", "pea", "bug", "gag", "mil", "jig", "hub", "low", "did", "tin", "get", "gte", "sox", "lei", "mig", "fig", "lon", "use", "ban", "flo", "nov", "jut", "bag", "mir", "sty", "lap", "two", "ins", "con", "ant", "net", "tux", "ode", "stu", "mug", "cad", "nap", "gun", "fop", "tot", "sow", "sal", "sic", "ted", "wot", "del", "imp", "cob", "way", "ann", "tan", "mci", "job", "wet", "ism", "err", "him", "all", "pad", "hah", "hie", "aim", "ike", "jed", "ego", "mac", "baa", "min", "com", "ill", "was", "cab", "ago", "ina", "big", "ilk", "gal", "tap", "duh", "ola", "ran", "lab", "top", "gob", "hot", "ora", "tia", "kip", "han", "met", "hut", "she", "sac", "fed", "goo", "tee", "ell", "not", "act", "gil", "rut", "ala", "ape", "rig", "cid", "god", "duo", "lin", "aid", "gel", "awl", "lag", "elf", "liz", "ref", "aha", "fib", "oho", "tho", "her", "nor", "ace", "adz", "fun", "ned", "coo", "win", "tao", "coy", "van", "man", "pit", "guy", "foe", "hid", "mai", "sup", "jay", "hob", "mow", "jot", "are", "pol", "arc", "lax", "aft", "alb", "len", "air", "pug", "pox", "vow", "got", "meg", "zoe", "amp", "ale", "bud", "gee", "pin", "dun", "pat", "ten", "mob");
new WordLadderII().findLadders("cet", "ism", dic);
}
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
dictionary.addAll(wordList);
bfs(beginWord, endWord, wordList);
List<String> path = new ArrayList<>();
path.add(beginWord);
dfs(beginWord, endWord, path);
System.out.println(result);
return result;
}
/**
* Bfs
*
* @param beginWord begin word
* @param endWord end word
* @param wordList wordlist
*/
private void bfs(String beginWord, String endWord, List<String> wordList) {
queue.offer(beginWord);
minDistance.put(beginWord, 0);
while (!queue.isEmpty()) {
String currWord = queue.poll();
StringBuilder childSb = new StringBuilder(currWord);
for (int j = 0, ln = childSb.length(); j < ln; j++) {
for (int i = 0, l = CONST.length(); i < l; i++) {
char old = childSb.charAt(j);
childSb.replace(j, j + 1, String.valueOf(CONST.charAt(i)));
String child = childSb.toString();
if (dictionary.contains(child)) {
if (minDistance.get(child) == null) {
minDistance.put(child, minDistance.get(currWord) + 1);
addChild(currWord, child);
if (!child.equals(endWord))
queue.offer(child);
} else {
if (minDistance.get(child) == (minDistance.get(currWord) + 1))
addChild(currWord, child);
}
}
childSb.replace(j, j + 1, String.valueOf(old));
}
}
}
}
/**
* Add child
*
* @param parent parent
* @param child child
*/
private void addChild(String parent, String child) {
Set<String> children = graph.get(parent);
if (children == null)
children = new HashSet<>();
children.add(child);
graph.put(parent, children);
}
/**
* Dfs to build path
*
* @param currWord node
* @param endWord endword
* @param path path
*/
private void dfs(String currWord, String endWord, List<String> path) {
if (currWord.equals(endWord)) {
result.add(new ArrayList<>(path));
} else {
Set<String> children = graph.get(currWord);
if (children != null) {
for (String c : children) {
path.add(c);
dfs(c, endWord, path);
path.remove(path.size() - 1);
}
}
}
}
}