[20.10] word ladder

1. Example
Breadth First Search

http://rangerway.com/way/leetcode-word-ladder-ii/
start = hit
end = cog
dict =[hot,dot,dog,lot,log,dof,mit,sit,set,mog,mig,seg,nax,max]



level 1: [hit]
level 2: [mit, sit, hot]
level 3: [mig, set, dot, lot]
level 4: [mog, seg, dof, dog, log]
level 5: [cog]

Return

  [["hit","hot","dot","dog","cog"],
   ["hit","hot","lot","log","cog"],
   ["hit","mit","mig","mog","cog"]]

Input: DAMP, LIKE
Output: DAMP-> LAMP->LIMP->LIME->LIKE
 
http://www.programcreek.com/2012/12/leetcode-word-ladder/

25*L , L is the length of the string, every letter has 25 possibility
so there are total 25*L possibilities


2. Implementation

// Dictionary 26^L or size(dict)
// Time:O( min(26^L, size(dict)) ), Space:O( min(26^L, size(dict) )  ) 

// Time :O(m*m)

public List wordLadder(  String startWord, String stopWord, Set dictionary )
{



        List res = new ArrayList();
        //validate the input
        //if ( startWord == null || stopWord == null || dictionary == null )  
        if ( stratWord == null || stratWord.length() ==0 || stopWord == null || stopWord.length() ==0 || startWOrd.length() != stopWord.length() || dictionary == null )
             return res;




       
        startWord = startWord.toLowerCase();
        stopWord = stopWord.toLowerCase();
        LinkedList queue = new LinkedList();
        HashSet visited = new HashSet();
        int lastNum = 1;
        int curNum = 0;
        int level =1;
        queue.offer(startWord);
        visited.offer(startWord);


        


        while ( !queue.isEmpty() )
        {



             String cur = queue.poll();
             lastNum--;


             
             for ( int i = 0 ; i < cur.legnth(); i++ )
             {
                 char[] charCur = cur.toCharArray();
                 for ( char c='a'; c < 'z';c++ )
                 {
                     charCur[i] = c;
                     String temp = new String(charCur);



                     if (temp.equals(end))
                     {
                             list.add(end);
                             return list;
                             //return level+1;
                     }



                     if ( dict.contains(temp) && !visited.contains(temp) )
                     {
                          curNum++; 
                          queue.offer(temp);
                          visited.add(temp);
                          list.add(temp);
                     }




                 }

             }



             if (lastNum == 0)
             {
                  lastNum = curNum;
                  curNum = 0;
                  level++;
             }
        }


        
       
        return null;



}

3. Similar one
http://blog.csdn.net/linhuanmars/article/details/23029973