1+ M
2+
3+ Brutle : 遍历所有26个字母 。
4+
5+ 方法2 :
6+ 用Trie 。 理应更快 . However implementation可能有点重复计算的地方 ，LeetCode timeout . 需要再做做 。
7+
8+ ```
19/*
210Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
311
@@ -124,3 +132,183 @@ else if (i == str.length() - 1) {
124132 }//END FOR I
125133 }
126134}
135+
136+
137+
138+
139+
140+
141+
142+ /*
143+ Use a new method in Trie:
144+ getChildrenMap(string s): get the children hashmap at last char of s.
145+ getCurrMap(s): get the hashmap where the last char of s is at.
146+
147+ However, still timeout in LeetCode. So there might be some case that's using extra calculation.
148+ It should ideally be faster than brutle force.
149+ */
150+ import java .io .*;
151+ import java .util .*;
152+
153+ class Solution {
154+
155+ class TrieNode {
156+ String str ;
157+ boolean isEnd ;
158+ boolean visited ;
159+ HashMap <Character , TrieNode > children ;
160+ public TrieNode () {
161+ this .isEnd = false ;
162+ this .visited = false ;
163+ this .str = "" ;
164+ children = new HashMap <Character , TrieNode >();
165+ }
166+ }
167+
168+
169+
170+ public TrieNode root = new TrieNode ();
171+ public int leng = Integer .MAX_VALUE ;
172+ public int ladderLength (String beginWord , String endWord , Set <String > wordList ) {
173+ if (beginWord == null || endWord == null || beginWord .length () != endWord .length ()
174+ || wordList == null || wordList .size () == 0 ) {
175+ return 0 ;
176+ }
177+
178+ //build Trie
179+ for (String s : wordList ) {
180+ insert (s );
181+ }
182+ dfs (beginWord , endWord , 1 );
183+
184+ return leng ;
185+ }
186+
187+ public void dfs (String start , String end , int step ) {
188+ if (step >= leng ) {
189+ return ;
190+ }
191+
192+ if (compare (start , end ) == 0 ) {
193+ leng = Math .min (leng , step );
194+ return ;
195+ }
196+ //catch last step, so it covers the case where last change is not in dictionary
197+ if (compare (start , end ) == 1 ) {
198+ leng = Math .min (leng , step + 1 );
199+ return ;
200+ }
201+
202+ for (int i = 0 ; i < start .length (); i ++) {//try to replace every index
203+ String s = start .substring (0 , i + 1 );
204+ HashMap <Character , TrieNode > candidates = getCurrentMap (s );
205+
206+ //If char(i) not in dictinary, go back up one level,
207+ //try to find all possible children candidates of previous char. Keep going with the process
208+ if (candidates == null ) {
209+ s = start .substring (0 , i );
210+ candidates = getChildrenMap (s );
211+ //If prev char is not found neither, fail it.
212+ //Example, when 'b' in "ab" not found, try to find 'a' and its children; however, if 'a' not found neither, cut it off here
213+ if (candidates == null ) {
214+ continue ;
215+ }
216+ }
217+
218+ //Replace char at i with all candidates existing in Trie dictionary
219+ for (Map .Entry <Character , TrieNode > entry : candidates .entrySet ()) {
220+ char c = entry .getKey ();
221+ String newStr = start .substring (0 ,i ) + c + start .substring (i +1 );
222+ if (c != start .charAt (i ) && !entry .getValue ().visited ) {
223+ candidates .get (c ).visited = true ;
224+ dfs (newStr , end , step + 1 );
225+ }
226+ }
227+ }
228+ }
229+
230+ /**************************Trie section *********************/
231+ //In this problem ,didin't use startWith() or search().
232+ //Instead, use a similar function, getChildrenMap. See below
233+
234+ public void insert (String s ){
235+ char [] arr = s .toCharArray ();
236+ TrieNode node = root ;
237+ for (int i = 0 ; i < arr .length ; i ++) {
238+ char c = arr [i ];
239+ if (!node .children .containsKey (c )) {
240+ node .children .put (c , new TrieNode ());
241+ }
242+ node = node .children .get (c );
243+ if (i == arr .length - 1 ) {
244+ node .isEnd = true ;
245+ node .str = s ;
246+ }
247+ }
248+ }
249+
250+ /*Return the HashMap where the last char of s is in*/
251+ public HashMap <Character , TrieNode > getCurrentMap (String s ) {
252+ char [] arr = s .toCharArray ();
253+ TrieNode node = root ;
254+ for (int i = 0 ; i < arr .length ; i ++) {
255+ char c = arr [i ];
256+ if (!node .children .containsKey (c )) {
257+ return null ;
258+ }
259+ if (i == arr .length - 1 ) {
260+ return node .children ;
261+ }
262+ node = node .children .get (c );
263+ }
264+ return null ;
265+ }
266+
267+ /*Return the children HashMap of the last char*/
268+ public HashMap <Character , TrieNode > getChildrenMap (String s ) {
269+ if (s == null || s .length () == 0 ) {
270+ return root .children ;
271+ }
272+ char [] arr = s .toCharArray ();
273+ TrieNode node = root ;
274+ for (int i = 0 ; i < arr .length ; i ++) {
275+ char c = arr [i ];
276+ if (!node .children .containsKey (c )) {
277+ return null ;
278+ }
279+ node = node .children .get (c );
280+ }
281+ return node .children ;
282+ }
283+
284+ //Helper to comapre string and return the difference if not <= 1
285+ public int compare (String s1 , String s2 ) {
286+ int count = 0 ;
287+ for (int i = 0 ; i < s1 .length (); i ++) {
288+ count += s1 .charAt (i ) != s2 .charAt (i ) ? 1 : 0 ;
289+ if (count > 1 ) {
290+ return count ;
291+ }
292+ }
293+ return count ;
294+ }
295+
296+
297+ public static void main (String [] args ) {
298+ String beginWord = "hit" ;//"hit";
299+ String endWord = "cog" ;
300+ Set <String > set = new HashSet <String >();
301+ set .add ("hot" ); set .add ("dot" ); set .add ("dog" ); set .add ("lot" ); set .add ("log" );
302+
303+
304+ Solution sol = new Solution ();
305+ int leng = sol .ladderLength (beginWord , endWord , set );
306+
307+ System .out .println ("rst " + leng );
308+ System .out .println ("END" );
309+ }
310+
311+ }
312+
313+
314+ ```
0 commit comments