127. Word Ladder

Given two words beginWord and endWord, and a dictionary wordList, return the length of the 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.

Return 0 if there is no such transformation sequence.

 

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.

 

Constraints:

  • 1 <= beginWord.length <= 100
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWordendWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the strings in wordList are unique.

Rust Solution

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

impl Solution {
    fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
        let n = begin_word.len();
        let mut unused_set: HashSet<Vec<u8>> = word_list
            .into_iter()
            .map(|s| s.as_bytes().to_vec())
            .collect();
        let begin_word = begin_word.as_bytes().to_vec();
        let end_word = end_word.as_bytes().to_vec();
        if !unused_set.contains(&end_word) {
            return 0;
        }
        let begin_list = vec![begin_word];
        let end_list = vec![end_word];
        let mut begin_set: HashSet<Vec<u8>> = HashSet::from_iter(begin_list);
        let mut end_set: HashSet<Vec<u8>> = HashSet::from_iter(end_list);
        let mut left_set: &mut HashSet<Vec<u8>> = &mut begin_set;
        let mut right_set: &mut HashSet<Vec<u8>> = &mut end_set;
        let mut ladder = 1;
        while !left_set.is_empty() {
            ladder += 1;
            let mut next_set: HashSet<Vec<u8>> = HashSet::new();
            for s in left_set.iter() {
                let mut v: Vec<u8> = s.to_vec();
                for i in 0..n {
                    let c = v[i];
                    for j in 0..26 {
                        v[i] = b'a' + j;
                        if right_set.contains(&v) {
                            return ladder;
                        }
                        if unused_set.contains(&v) {
                            unused_set.remove(&v);
                            next_set.insert(v.to_vec());
                        }
                    }
                    v[i] = c;
                }
            }
            *left_set = next_set;
            if left_set.len() > right_set.len() {
                std::mem::swap(&mut left_set, &mut right_set)
            }
        }
        0
    }
}

#[test]
fn test() {
    let begin_word = "hit".to_string();
    let end_word = "cog".to_string();
    let word_list = vec_string!["hot", "dot", "dog", "lot", "log", "cog"];
    assert_eq!(Solution::ladder_length(begin_word, end_word, word_list), 5);
    let begin_word = "hit".to_string();
    let end_word = "cog".to_string();
    let word_list = vec_string!["hot", "dot", "dog", "lot", "log"];
    assert_eq!(Solution::ladder_length(begin_word, end_word, word_list), 0);
}

Having problems with this solution? Click here to submit an issue on github.