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