[数据结构与算法]LeetCode每日一题(Word Ladder II)

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].
Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
Output: [[“hit”,“hot”,“dot”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]
Explanation: There are 2 shortest transformation sequences:
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”
Example 2:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
Output: []
Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 1000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.

个人认为这题的关键点是BFS, 能想到这基本这题就算解完了。不知道用DFS能不能解出来，但是我觉得会很复杂。

代码(Rust):

use std::collections::HashSet;
use std::iter::FromIterator;

impl Solution {
    fn check_word(w1: &String, w2: &String) -> bool {
        let mut count = 0;
        for (c1, c2) in w1.chars().zip(w2.chars()) {
            if c1 != c2 {
                count += 1;
            }
            if count == 2 {
                return false;
            }
        }
        return count == 1;
    }

    fn bfs(result: Vec<Vec<String>>, visited: HashSet<String>, end_word: &String, word_list: &Vec<String>) -> Vec<Vec<String>> {
        let mut res = Vec::new();
        let mut vis = HashSet::new();
        for l in result.clone() {
            let last = l.last().unwrap();
            if last == end_word {
                res.push(l.clone());
                continue;
            }
            for w in word_list {
                if Solution::check_word(last, w) && !visited.contains(w) {
                    let mut ll = l.clone();
                    ll.push(w.clone());
                    res.push(ll);
                    vis.insert(w.clone());
                }
            }
        }
        if vis.len() == 0 {
            return result;
        }
        let v: HashSet<String> = visited.union(&vis).map(|s| s.clone()).collect();
        Solution::bfs(res, v, end_word, word_list)
    }

    pub fn find_ladders(begin_word: String, end_word: String, word_list: Vec<String>) -> Vec<Vec<String>> {
        let result = vec![vec![begin_word.clone()]];
        let visited = HashSet::from_iter(vec![begin_word.clone()].into_iter());
        let res = Solution::bfs(result, visited, &end_word, &word_list);
        res.into_iter().filter(|l| l.last().unwrap() == &end_word).collect()
    }
}