One HashMap, one queue, with comment


  • 0
    Z

    Actually we could consider this problem as the shortest path problem in a graph. So we could use the idea of Dijkstra shortest path algorithm to solve it. Every time we search the next layer until we reach the end point.

    public class Solution {
            private class WTN
            {
                LinkedList<WTN> pre;
                String cur = new String();
                int step;
                public WTN(WTN node, String s, int step)
                {
                    this.cur = new String(s);
                    this.step = step;
                    this.pre = new LinkedList<WTN>();
                    pre.add(node);
                }
            }
            public List<List<String>> findLadders(String beginWord, String ew, Set<String> wordList) {
                List<List<String>> ret = new LinkedList<>();
                LinkedList<WTN> queue = new LinkedList<>(); // layer we will travel
                HashMap<String, WTN> set = new HashMap<>(); // point set which we have alread reached
                int min = Integer.MAX_VALUE;
                boolean next = false;
                WTN head = new WTN(null, beginWord, 0);     // to build graph
                
                queue.addLast(head);
                set.put(beginWord, head);
                
                while (!queue.isEmpty())
                {
                    WTN curr = queue.removeFirst();
                    int step = curr.step;
                    if (step + 1 > min) break;
                    next = false;
                    // which position to change 
                    for (int i = 0; !next && i < curr.cur.length(); i++) {
                		StringBuilder temp = new StringBuilder(curr.cur);
                		// change into which letter in position i
                        for (char c = 'a'; c <= 'z'; c ++) {
                            temp.setCharAt(i, c);
                            String nw = temp.toString();
                            if (nw.equals(ew)){
                                LinkedList<String> listT = new LinkedList<>();
                                listT.addLast(ew);
                                getPath(curr, ret, listT); // backtrack
                                min = step + 1;
                                next = true;
                                break;
                            }
                            
                            if (wordList.contains(nw)) {
                                if (!set.containsKey(nw)){
                                    WTN nn = new WTN(curr, nw, step + 1);
                                    set.put(nw, nn);
                                    queue.add(nn);
                                }
                                else if (set.get(nw).step == step + 1)
                                    set.get(nw).pre.add(curr);
                            }
                        } // end of letter choice
                    } // end of position choice
                } // end of while
                return ret;
            }
            
            private void getPath(WTN bw, List<List<String>> ret, LinkedList<String> list)
            {
                if (bw == null){
                    ret.add(new LinkedList(list));
                    return;
                }
                
                list.addFirst(bw.cur);
                for (WTN node : bw.pre)
                    getPath(node, ret, list);
                list.removeFirst();
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.