My java BFS solution


  • 4
    T

    basically first u construct a graph in which the nodes are the words in dictionary, and two nodes are connected if they are different only by one char.

    then we find the min paths from starting word to ending word. this is done using BFS. at each node we trace back to upstream using a list of possible upstream nodes.

    public class Solution {
        List<List<String>> result = new ArrayList<List<String>>();
        List<Integer> partialAnswer = new ArrayList<Integer>();
        ArrayList<String> dictionary;
        public List<List<String>> findLadders(String start, String end, Set<String> dict) {
           ArrayList<String> words = new ArrayList<String>();
           words.addAll(dict);
           
           dictionary = words;
           
           boolean ok[][] = new boolean[words.size()][words.size()];
           for(int i=0;i<words.size();i++) {
               for(int j=0;j<words.size();j++) {
                   if (i==j) ok[i][j] = true;
                   else 
                    ok[i][j] = findWordsDistance(words.get(i), words.get(j));
               }
           }
           
           // bfs traversal
           int startingIdx = words.indexOf(start);
           int endingIdx = words.indexOf(end);
           
           int used[] = new int[words.size()];
           ArrayList<Integer> incoming[] = new ArrayList[words.size()];
           for(int i=0;i<words.size();i++)
            incoming[i] = new ArrayList<Integer>();
            
           Queue<Integer> q = new LinkedList<Integer>();
           q.add(startingIdx);
           used[startingIdx] = 1;
           while( q.size() != 0 ) {
               Integer startFrom = q.poll();
               if (startFrom == endingIdx)
                break;
               for(int i=0;i<words.size();i++){
                   if (ok[startFrom][i]) {
                       if (used[i]==0) {
                        q.add(i);
                        used[i] = used[startFrom] +1;
                       }
                       if (used[startFrom] +1 <= used[i])
                       incoming[i].add(startFrom);
                   }
               }
           }
           
           // trace back
           trace(incoming, startingIdx, endingIdx);
           
           return result;
        }
        
        void trace(List<Integer>[] incoming, int start, int end) {
            if ( start == end) {
                // collect
                ArrayList<String> list = new ArrayList<String>();
                            list.add(dictionary.get(end));
    
                for(int i=partialAnswer.size()-1;i>=0;i--)
                    list.add(dictionary.get(partialAnswer.get(i)));
                result.add(list);
                return;
            }
            
            partialAnswer.add(end);
            for(int upstream : incoming[end]) {
                trace(incoming, start, upstream);
            }
            partialAnswer.remove(partialAnswer.size()-1);
        }
        
        boolean findWordsDistance(String a, String b) {
            if (a.length() != b.length()) return false;
            int diff = 0;
            for(int i=0;i<a.length();i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    if (++diff >1)
                        return false;
                }
            }
            return true;
        }
    }

Log in to reply
 

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