My Easy to Understand Single BFS Java


  • 1
    H
        public class Solution {
            public List<List<String>> findLadders(String begin, String end, Set<String> dict) {
                List<List<String>> ret = new ArrayList<>();
                Queue<Item> queue = new LinkedList<>();
                Item first = new Item(begin, 1);
                queue.add(first);
                first.list.add(begin);
    
                Set<String> visited = new HashSet<>();
    
                int min = Integer.MAX_VALUE;
                int preSteps = 0;
                while (!queue.isEmpty()) {
                    Item cur = queue.poll();
                    if (cur.s.equals(end)) {
                        if (cur.n <= min) {
                            min = cur.n;
                            ret.add(cur.list);
                        }
                    }
                    if (cur.n > min)    break;
                    if (cur.n > preSteps)   dict.removeAll(visited);
                    preSteps = cur.n;
    
                    char[] cc = cur.s.toCharArray();
                    for (int i=0; i<cc.length; i++) {
                        char old = cc[i];
                        for (char j='a'; j<='z'; j++) {
                            cc[i] = j;
                            String newS = new String(cc);
                            if (cur.s.equals(newS) || !dict.contains(newS)) continue;
                            visited.add(newS);
                            Item newItem = new Item(newS, cur.n+1);
                            newItem.list.addAll(cur.list);
                            newItem.list.add(newS);
                            queue.add(newItem);
                        }
                        cc[i] = old;
                    }
                }
                return ret;
            }
    
            class Item {
                String s;
                int n;
                List<String> list;
                public Item(String s, int n) {
                    this.s = s;
                    this.n = n;
                    list = new ArrayList<>();
                }
            }
        }

Log in to reply
 

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