aboutsummaryrefslogtreecommitdiff
path: root/other/min_genetic_mutation.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_genetic_mutation.rs')
-rw-r--r--other/min_genetic_mutation.rs53
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
+ }
+}