Leetcode(127) Word Ladder

发表于 | 分类于

Description

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 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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
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的题，即每次遍历26个字母替换的所有情况，如果在list里则入队，同时统计更改的步数，步数采用HashMap存储。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wordSet = new HashSet<>(wordList);
        if(!wordSet.contains(endWord)){
            return 0;
        }
        HashMap<String,Integer> lengthMap = new HashMap<>();
        lengthMap.put(beginWord, 1);
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        while(!q.isEmpty()){
            String word = q.poll();
            for(int i = 0; i < word.length() ; i++){
                String newWord = word;
                for(char j = 'a'; j <= 'z' ;j++){
                    newWord = newWord.substring(0, i) + j + newWord.substring(i + 1);
                    if(wordSet.contains(newWord) && newWord.equals(endWord)){
                        return lengthMap.get(word) + 1;
                    }
                    if(wordSet.contains(newWord) && !lengthMap.containsKey(newWord)){
                        q.offer(newWord);
                        lengthMap.put(newWord,lengthMap.get(word) + 1);
                    }
                }
            }
        }
        return 0;
    }
}