2015年10月8日星期四

Leetcode 127 Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
Solution 1: Use BFS and a set to track each ladder with solve it. 
 public class Solution {  
   public int ladderLength(String beginWord, String endWord, Set<String> wordList) {  
     Set<String> set=new HashSet<>();  
     set.add(beginWord);  
     int d=0;  
     while (!set.isEmpty()) {  
       wordList.removeAll(set);  
       Set<String> nextSet=new HashSet<>();  
       for (String s:set) {  
         char[] c=s.toCharArray();  
         for (int i=0; i<c.length; i++) {  
           char temp=c[i];  
           for (char r='a'; r<='z'; r++) {  
             c[i]=r;  
             String x=new String(c);  
             if (x.equals(endWord)) return d+2;  
             else if (wordList.contains(x)) nextSet.add(x);  
           }  
           c[i]=temp;  
         }  
       }  
       set=nextSet;  
       d++;  
     }  
     return 0;  
   }  
 }  

没有评论:

发表评论