My BFS Solution


  • 0
    B
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (beginWord.equals(endWord)) return 2;
            if (wordList.size()==0) return 0;
    
            List<String> list = new ArrayList<>();
            list.add(beginWord);
            int count = 1;
            while(!list.isEmpty()){
                List<String> next = new ArrayList<>();
                List<Integer> toDeleteIndex = new ArrayList<>();
                count++;
                for(String a:list){
                    for(int i=0;i<wordList.size();i++){
                        String b = wordList.get(i);
                        if (b.equals("")) continue;
                        if (isRight(a,b)){
                            if (b.equals(endWord)){
                                return count;
                            }else{
                                next.add(b);
                            }
                            toDeleteIndex.add(i);
                        }
                    }
                    for(int index:toDeleteIndex){
                        wordList.set(index,"");
                    }
                }
                list = next;
                //System.out.println(list);
            }
            return 0;
        }
        private boolean isRight(String aString,String bString){
            int count = 0;
           for(int i=0;i<aString.length();i++){
               if (aString.charAt(i)!=bString.charAt(i)) count++;
               if (count>1) break;
           }
            return count==1;
        }

Log in to reply
 

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