127.Word-Ladder

127. Word Ladder

题目地址

https://leetcode.com/problems/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:

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.

代码

Approach #1 BFS

1> 获取邻接表

2> 采用BFS Queue> queue， 最后返回level + 1

Complexity Analysis

• Time Complexity: O(M×N), where M is the length of words and N is the total number of words in the input word list. Finding out all the transformations takes M iterations for each of the N words. Also, breadth first search in the worst case might go to each of the N words.

• Space Complexity: O(M×N), to store all M transformations for each of the N words, in the all_combo_dict dictionary. Visited dictionary is of N size. Queue for BFS in worst case would need space for all N words.

class Solution {
  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    int L = beginWord.length();
    // map: a*c = > abc
    Map<String, List<String>> allComboDict = new HashMap<>();
    wordList.forEach(
        word -> {
       for (int i = 0; i < L; i++) {
         String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
         allComboDict.putIfAbsent(newWord, new ArrayList());
         allComboDict.get(newWord).add(word);
       }
     });

    HashSet<String> visited = new HashSet<String>();
    visited.add(beginWord);

    Queue<Pair<String, Integer>> queue = new LinkedList<>();
    queue.add(new Pair(beginWord, 1));
    while (!queue.isEmpty()) {
      Pair<String, Integer> node = queue.poll();
      String word = node.getKey();
      int level = node.getValue();
      for (int i = 0; i < L; i++) {
        String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

        for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
          if (adjacentWord.equals(endWord)) {
            return level + 1;
          }

          if (!visited.contains(adjacentWord)) {
            visited.add(adjacentWord);
            queue.add(new Pair(adjacentWord, level + 1));
          }
        }
      }
    }

    return 0;
  }
}

Approach #2 BFS

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (wordList == null) return 0;
    if (beginWord.equals(endWord)) return 1;

    HashSet<String> dict = new HashSet<String>(wordList);
    // dict.add(beginWord);
    // dict.add(endWord); leetcode OJ中不包含结果单词不能通过

    HashSet<String> visit = new HashSet<String>();
    Queue<String> queue = new LinkedList<String>();
    queue.offer(beginWord);
    visit.add(beginWord);

    int transformation = 1;
    while (!queue.isEmpty()) {
      transformation++;
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        String word = queue.poll();
        for (String nextWord : getNextWords(word, dict)) {
          if (visit.contains(nextWord)) {
            continue;
          }
          if (nextWord.equals(endWord)) {
            return transformation;
          }

          visit.add(nextWord);
          queue.offer(nextWord);
        }
      }
    }
    return 0;
  }

  private ArrayList<String> getNextWords(String word, Set<String> dict) {
    ArrayList<String> nextWords = new ArrayList<String>();
    for (char c = 'a'; c <= 'z'; c++) {
      for (int i = 0; i < word.length(); i++) {
        if (c == word.charAt(i)) {
          continue;
        }
        String nextWord = replace(word, i, c);
        if (dict.contains(nextWord)) {
          nextWords.add(nextWord);
        }
      }
    }
    return nextWords;
  }

  private String replace(String s, int index, char c) {
    char[] chars = s.toCharArray();
    chars[index] = c;
    return new String(chars);
  }

}