leetcode_rust/
open_the_lock.rs

1#![allow(dead_code)]
2
3pub fn open_lock(deadends: Vec<String>, target: String) -> i32 {
4    use std::collections::HashSet;
5    use std::collections::LinkedList;
6
7    let mut visited = HashSet::new();
8    let mut dead_ends = HashSet::new();
9    let target = target.into_bytes();
10    for s in deadends {
11        dead_ends.insert(s.into_bytes());
12    }
13    let mut q = LinkedList::new();
14    q.push_back((String::from("0000").into_bytes(), 0));
15
16    while !q.is_empty() {
17        let cur = q.pop_front().unwrap();
18        match dead_ends.get(&cur.0) {
19            Some(_) => {
20                continue;
21            }
22            None => {}
23        }
24
25        match visited.get(&cur.0) {
26            Some(_) => {
27                continue;
28            }
29            None => {
30                visited.insert(cur.0.clone());
31            }
32        }
33        if target == cur.0 {
34            return cur.1;
35        }
36        let neighbors = get_neighbors(cur.0);
37
38        for n in neighbors {
39            q.push_back((n, cur.1 + 1));
40        }
41    }
42
43    -1
44}
45
46fn get_neighbors(s: Vec<u8>) -> Vec<Vec<u8>> {
47    let mut neighbors = Vec::with_capacity(8);
48    let origin = s.clone();
49    for (i, &c) in s.iter().enumerate() {
50        let n;
51        if c == b'9' {
52            n = (b'8', b'0');
53        } else if c == b'0' {
54            n = (b'9', b'1');
55        } else {
56            n = (c + 1, c - 1);
57        }
58
59        let mut new = origin.clone();
60        new[i] = n.0;
61        neighbors.push(new);
62
63        let mut new = origin.clone();
64        new[i] = n.1;
65        neighbors.push(new);
66    }
67
68    neighbors
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test1() {
77        let dead_ends = vec![
78            String::from("0201"),
79            String::from("0101"),
80            String::from("0102"),
81            String::from("1212"),
82            String::from("2002"),
83        ];
84
85        let res = open_lock(dead_ends, String::from("0202"));
86        assert_eq!(res, 6);
87
88        let dead_ends = vec![String::from("8888")];
89
90        let res = open_lock(dead_ends, String::from("0009"));
91        assert_eq!(res, 1);
92    }
93}
leetcode_rust/open_the_lock.rs

leetcode_rust/
open_the_lock.rs
