Share my solution in java use 2 queues~


  • 3
    W

    The tricky part of this question is: how to make sure the length is increased correctly for each path.
    e.g. hot can have 3 variations: tot, hat, hop and only hop can transfer to pop(endWord).

    So start from hot, there are 3 paths to next step, in order to make sure each step are increased correctly, we can use a queue for length, so it records the length of each path without mess it up :)

    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
            Queue<String> wordQ=new LinkedList<String>();
            Queue<Integer> lengthQ=new LinkedList<Integer>();
            wordQ.offer(beginWord);
            lengthQ.offer(1);
            wordDict.remove(beginWord);
            
            while(wordQ.peek()!=null){
                String currentWord=wordQ.poll();
                int len=lengthQ.poll();
                if(currentWord.equals(endWord)) return len;
                
                for(int i=0;i<currentWord.length();i++){    //for each char in the word
                    char[] charArray=currentWord.toCharArray();
                    for(int j=0;j<26;j++){                  //change from a to z
                        charArray[i]=(char)('a'+j);
                        String tmp=String.valueOf(charArray);
                        if(wordDict.contains(tmp)){
                            wordDict.remove(tmp);
                            wordQ.offer(tmp);
                            lengthQ.offer(len+1);
                        }
                    }
                }
            }
            return 0;
        }

Log in to reply
 

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