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, 0 insertions, 53 deletions
diff --git a/other/min_genetic_mutation.rs b/other/min_genetic_mutation.rs
deleted file mode 100644
index 1362636..0000000
--- a/other/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
- }
-}