aboutsummaryrefslogtreecommitdiff
path: root/min_genetic_mutation.rs
blob: 13626369aafcd7f6840f187e1fe981d92c980901 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
use std::collections::HashSet;
struct Solution;

impl Solution {
    pub fn min_mutation(start: String, end: String, mut bank: Vec<String>) -> i32 {
        match bank.iter().position(|w| end.eq(w)) {
            None => return -1,
            Some(idx) => bank.swap_remove(idx)
        };
        let (mut left, mut right, mut next) = (HashSet::new(), HashSet::new(), HashSet::new());
        left.insert(start);
        right.insert(end);
        let mut len = 0;
        while !left.is_empty() && !right.is_empty() {
            if left.len() > right.len() {
                std::mem::swap(&mut left, &mut right);
            }
            for w in left.drain() {
                let mut idx = 0;
                for word in right.iter() {
                    if Self::is_adjacent(&w, word.as_str()) {
                        return len + 1;
                    }
                }
                while idx < bank.len() {
                    if !is_adjacent(&w, &bank[idx]) {
                        idx += 1;
                        continue;
                    }
                    let neighbor = bank.swap_remove(idx);
                    next.insert(neighbor);
                }
            }
            std::mem::swap(&mut left, &mut next);
            len += 1;
        }
        -1
    }
    fn is_adjacent(a: &str, b: &str) -> bool {
        let (a, b) = (a.as_bytes(), b.as_bytes());
        assert_eq!(a.len(), b.len());
        let mut diff = 0;
        for idx in 0..a.len() {
            if a[idx] != b[idx] {
                diff += 1;
            }
            if diff > 1 {
                break;
            }
        }
        diff == 1
    }
}