diff options
Diffstat (limited to 'min_genetic_mutation.rs')
-rw-r--r-- | min_genetic_mutation.rs | 53 |
1 files changed, 0 insertions, 53 deletions
diff --git a/min_genetic_mutation.rs b/min_genetic_mutation.rs deleted file mode 100644 index 1362636..0000000 --- a/min_genetic_mutation.rs +++ /dev/null @@ -1,53 +0,0 @@ -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 - } -} |