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
}
}
|