001package algs41; 002import stdlib.*; 003import algs35.XIndexSET; 004/* *********************************************************************** 005 * Compilation: javac WordLadder.java 006 * Execution: java WordLadder word1 word2 < wordlist.txt 007 * Dependencies: Graph.java IndexSET.java In.java BreadthFirstPaths.java 008 * 009 * Data files: http://www.cs.princeton.edu/algs4/41undirected/words5.txt 010 * http://www.cs.princeton.edu/algs4/41undirected/words6.txt 011 * http://www.cs.princeton.edu/algs4/41undirected/words5-knuth.txt 012 * 013 * java WordLadder flirt break < words5.txt 014 * length = 11 015 * flirt 016 * flint 017 * fling 018 * cling 019 * clink 020 * click 021 * clock 022 * cloak 023 * croak 024 * creak 025 * break 026 * 027 * % java WordLadder allow brown < words5.txt 028 * NOT CONNECTED 029 * 030 * % java WordLadder white house < words5.txt 031 * length = 18 032 * white 033 * while 034 * whale 035 * shale 036 * shake 037 * slake 038 * slate 039 * plate 040 * place 041 * peace 042 * peach 043 * poach 044 * coach 045 * couch 046 * cough 047 * rough 048 * rouge 049 * rouse 050 * house 051 * 052 * % java WordLadder white house < words5-knuth.txt 053 * length = 9 054 * white 055 * whits 056 * shits 057 * shots 058 * soots 059 * roots 060 * routs 061 * route 062 * rouse 063 * house 064 * 065 *************************************************************************/ 066 067public class XWordLadder { 068 069 // return true if two strings differ in exactly one letter 070 public static boolean isNeighbor(String a, String b) { 071 assert a.length() == b.length(); 072 int differ = 0; 073 for (int i = 0; i < a.length(); i++) { 074 if (a.charAt(i) != b.charAt(i)) differ++; 075 } 076 return (differ == 1); 077 } 078 079 public static void main(String[] args) { 080 args = new String[] { "flirt", "break" }; StdIn.fromFile ("data/words5.txt"); 081 //args = new String[] { "white", "house" }; StdIn.fromFile ("data/words5.txt"); 082 //args = new String[] { "allow", "brown" }; StdIn.fromFile ("data/words5.txt"); 083 //args = new String[] { "white", "house" }; StdIn.fromFile ("data/words5-knuth.txt"); 084 085 String from = args[0]; 086 String to = args[1]; 087 if (from.length() != to.length()) 088 throw new Error("Words have different lengths"); 089 090 /* ***************************************************************** 091 * Read a list of strings, all of the same length. 092 * At most 10000 words supported here. 093 *******************************************************************/ 094 XIndexSET<String> words = new XIndexSET<>(); 095 while (!StdIn.isEmpty()) { 096 String word = StdIn.readString(); 097 if (word.length() != from.length()) 098 throw new Error("Words have different lengths"); 099 words.add(word); 100 } 101 System.err.println("Finished reading word list"); 102 103 /* ***************************************************************** 104 * Insert connections between neighboring words into graph. 105 * This construction process can be improved from LN^2 to 106 * L N log N by sorting, where L = length of words. 107 * 108 * We insert two copies of each edge, but this is easily avoided 109 * by checking if word1.compareTo(word2) < 0 110 * 111 *******************************************************************/ 112 Graph G = new Graph(words.size()); 113 for (String word1 : words.keys()) { 114 for (String word2 : words.keys()) { 115 if (isNeighbor(word1, word2)) { 116 G.addEdge(words.indexOf(word1), words.indexOf(word2)); 117 } 118 } 119 } 120 System.err.println("Finished building graph"); 121 122 /* ***************************************************************** 123 * Run breadth first search 124 *******************************************************************/ 125 BreadthFirstPaths bfs = new BreadthFirstPaths(G, words.indexOf(from)); 126 //DepthFirstPaths bfs = new DepthFirstPaths(G, words.indexOf(from)); 127 if (bfs.hasPathTo(words.indexOf(to))) { 128 StdOut.println("length = " + bfs.distTo(words.indexOf(to))); 129 for (int v : bfs.pathTo(words.indexOf(to))) { 130 StdOut.println(words.keyOf(v)); 131 } 132 } 133 else StdOut.println("NOT CONNECTED"); 134 } 135}