Short AC Java BFS solution


  • 0
    M
    public int ladderLength(String start, String end, Set<String> dict) {
        if (transferable(start,end)){
            return 2;
        }
        Queue<String> que = new LinkedList<>();
        que.add(start);
        int length = 1,setSize = dict.size()
        while(!que.isEmpty()){
            length++;
            int size = que.size();
            for (int i = 0; i < size; i++){
                String done = que.remove();
                if (transferable(done,end)) return length;
                Iterator<String> dictIter = dict.iterator();
                while(dictIter.hasNext()){
                    String discovered = dictIter.next();
                    if (transferable(discovered,done)){
                        que.add(discovered);
                        dictIter.remove();
                    }
                }
            }
        }
        if (que.isEmpty()) return 0;
        return length;
    }
    public boolean transferable(String a, String b){
        int diffCount = 0;
        for (int i = 0; i < a.length(); i++){
            if (a.charAt(i) - b.charAt(i) != 0) diffCount++;
        }
        return diffCount <= 1;
    }

Log in to reply
 

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