|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- 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:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
- Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
- Example 1:
- Input:
- beginWord = "hit",
- endWord = "cog",
- wordList = ["hot","dot","dog","lot","log","cog"]
- Output: 5
- Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
- return its length 5.
- Example 2:
- Input:
- beginWord = "hit"
- endWord = "cog"
- wordList = ["hot","dot","dog","lot","log"]
- Output: 0
- Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
复制代码
BFS
- class Solution {
- public int ladderLength(String beginWord, String endWord, List<String> wordAsList) {
- if(!wordAsList.contains(endWord)){
- return 0;
- }
-
- Queue<String> beginSet = new LinkedList<String>();
- HashSet<String> wordList = new HashSet<String>(wordAsList);
-
- beginSet.add(beginWord);
- int level = 0;
-
- while(!beginSet.isEmpty()){
-
- int size = beginSet.size();
- for(int i = 0 ; i< size; i++){
- String word = beginSet.poll();
- if(word.equals(endWord)) return level+1;
- char[] wordset = word.toCharArray();
- for(int k = 0 ; k< wordset.length; k++){
- char temp = wordset[k];
- for(char j = 'a' ; j<= 'z'; j++){
- wordset[k] = j;
- String str = new String(wordset);
- if(wordList.contains(str)){
- wordList.remove(str);
- beginSet.add(str);
- }
- }
- wordset[k] = temp;
- }
- }
-
- level ++;
- }
-
- return 0;
- }
- }
复制代码
Bidirection BFS
- class Solution {
- public int ladderLength(String beginWord, String endWord, List<String> wordAsList) {
- if(!wordAsList.contains(endWord)){
- return 0;
- }
-
- Set<String> beginSet = new HashSet<String>();
- Set<String> endSet = new HashSet<String>();
-
- HashSet<String> wordList = new HashSet<String>(wordAsList);
-
- beginSet.add(beginWord);
- endSet.add(endWord);
- int level = 1;
-
- while(!beginSet.isEmpty() && !endSet.isEmpty()){
- if(beginSet.size() > endSet.size()){
- Set <String> temp = endSet;
- endSet = beginSet;
- beginSet = temp;
- }
-
- Set <String> temp = new HashSet<String>();
-
-
- for(String word : beginSet){
-
- char[] wordset = word.toCharArray();
- int len = beginWord.length();
- for(int k = 0 ; k< len; k++){
- char temp1 = wordset[k];
- for(char j = 'a' ; j<= 'z'; j++){
- wordset[k] = j;
- String str = new String(wordset);
-
- if(endSet.contains(str)) return level+1;
-
- if(!wordList.contains(str)) continue;
-
- wordList.remove(str);
- temp.add(str);
-
- }
- wordset[k] = temp1;
-
- }
- }
- Set <String> temp2 = beginSet;
- beginSet = temp;
- temp = temp2;
- level ++;
- }
-
- return 0;
- }
- }
复制代码 |
|