rustgym/leetcode/
_127_word_ladder.rs

1struct Solution;
2use std::collections::HashSet;
3use std::iter::FromIterator;
4
5impl Solution {
6    fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
7        let n = begin_word.len();
8        let mut unused_set: HashSet<Vec<u8>> =
9            HashSet::from_iter(word_list.into_iter().map(|s| s.as_bytes().to_vec()));
10        let begin_word = begin_word.as_bytes().to_vec();
11        let end_word = end_word.as_bytes().to_vec();
12        if !unused_set.contains(&end_word) {
13            return 0;
14        }
15        let begin_list = vec![begin_word];
16        let end_list = vec![end_word];
17        let mut begin_set: HashSet<Vec<u8>> = HashSet::from_iter(begin_list);
18        let mut end_set: HashSet<Vec<u8>> = HashSet::from_iter(end_list);
19        let mut left_set: &mut HashSet<Vec<u8>> = &mut begin_set;
20        let mut right_set: &mut HashSet<Vec<u8>> = &mut end_set;
21        let mut ladder = 1;
22        while !left_set.is_empty() {
23            ladder += 1;
24            let mut next_set: HashSet<Vec<u8>> = HashSet::new();
25            for s in left_set.iter() {
26                let mut v: Vec<u8> = s.to_vec();
27                for i in 0..n {
28                    let c = v[i];
29                    for j in 0..26 {
30                        v[i] = b'a' + j;
31                        if right_set.contains(&v) {
32                            return ladder;
33                        }
34                        if unused_set.contains(&v) {
35                            unused_set.remove(&v);
36                            next_set.insert(v.to_vec());
37                        }
38                    }
39                    v[i] = c;
40                }
41            }
42            *left_set = next_set;
43            if left_set.len() > right_set.len() {
44                std::mem::swap(&mut left_set, &mut right_set)
45            }
46        }
47        0
48    }
49}
50
51#[test]
52fn test() {
53    let begin_word = "hit".to_string();
54    let end_word = "cog".to_string();
55    let word_list = vec_string!["hot", "dot", "dog", "lot", "log", "cog"];
56    assert_eq!(Solution::ladder_length(begin_word, end_word, word_list), 5);
57    let begin_word = "hit".to_string();
58    let end_word = "cog".to_string();
59    let word_list = vec_string!["hot", "dot", "dog", "lot", "log"];
60    assert_eq!(Solution::ladder_length(begin_word, end_word, word_list), 0);
61}
rustgym/leetcode/_127_word_ladder.rs

rustgym/leetcode/
_127_word_ladder.rs
