127. Word LadderI/II

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

思路: 要求从初始单词到目标单词的最短路径, 要求每次只能变化每个单词的一个字母。 用BFS来解这道题目。 用一个hashmap来记录每个单词跟对应的距离. 用一个queue用来做bfs遍历。
BFS遍历过程: 1. 对queue进行poll操作拿到currentWord 2. 遍历currentWord的每个字符位置i, 同时对currentWord的每个位置上的字符进行’a’->’z’的替换,得到nextWord. 3. 先用endWord跟nextWord比较,如果相同,则找到,返回currentWord的长度+1. 如果不是endWord,如果满足wordList包含nextWord,同时hashMap中不存在这个nextWord,那么就将对应的nextWord存入hashMap,并放入queue。

复杂度: time O(n), space O(n)

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord == null || beginWord.length() == 0 || 
            endWord == null || endWord.length() == 0 || wordList.size() == 0) return 0;
        HashMap<String, Integer> dictMap = new HashMap<>();
        ArrayDeque<String> queue = new ArrayDeque<>();
        dictMap.put(beginWord, 1);
        queue.offer(beginWord);
        while(!queue.isEmpty()) {
            String currentWord = queue.poll();
            for (int i = 0; i < currentWord.length(); i++) {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    StringBuilder sb = new StringBuilder(currentWord);
                    sb.setCharAt(i, ch);
                    String nextWord = sb.toString();
                    if (endWord.equals(nextWord)) {
                        return dictMap.get(currentWord) + 1;
                    }
                    if (wordList.contains(nextWord) && !dictMap.containsKey(nextWord)) {
                        dictMap.put(nextWord, dictMap.get(currentWord) + 1);
                        queue.offer(nextWord);
                    }
                }
            }
        }
        return 0;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s