Word ladder

gistfile1.txt

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
      
      // check input
      if (!wordList.contains(endWord)) {
        return 0;
      }
      
      // We are going to use BFS to build the graph of the beginWord to endWord using
      // all words in the wordList
      
      Queue<String> levelBFS = new LinkedList();
      
      // The Queue is used to manage per level of the BFS
      Set<String> hasSeenWord = new HashSet();
      int level = 0;
      
      // add beginWord to start
      levelBFS.add(beginWord);
      hasSeenWord.add(beginWord);
      
      while (!levelBFS.isEmpty()) {
        
        final int levelCount = levelBFS.size();
        
        ++level;
        
        //System.out.println("Process level: " + level);
        
        // iterate current BFS level
        for (int i = 0; i < levelCount; i++) {
          
          String cur = levelBFS.poll();
          cur = cur.toLowerCase();
                   
          final char[] curCharArray = cur.toCharArray();
          for (int pos = 0; pos < curCharArray.length; pos++) {
            final char originalChar = curCharArray[pos];
            
            // Replace each letter with a-z and check if it is in the word list,
            // if it does check if it match, if not match simply add to Queue
            for (char r = 'a'; r <= 'z'; r++) {
              curCharArray[pos] = r;
              
              // check if it is a match
              String variance = new String(curCharArray);
              if (variance.equals(endWord)) {
                // got match, return level
                //System.out.println("Found at level: " + level);
                return level +  1;                
              } else {
                // else check in wordList, if yes and not in seen set, add it to 
                // queue
                if (wordList.contains(variance) && !hasSeenWord.contains(variance)) {
                  
                  //System.out.println("Add to BFS queue : " + variance);
                  hasSeenWord.add(variance);
                  levelBFS.add(variance);
                } else {
                  //System.out.println("Not added word : " + variance);
                }
              }
                        
            }
            
            // restore char
            curCharArray[pos] = originalChar;  
          }          
        }
      }
      
      return 0;
    }
}