rustgym 0.2.0

rustgym solutions
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

struct Solution;

use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
    fn k_similarity(a: String, b: String) -> i32 {
        let n = a.len();
        let a: Vec<char> = a.chars().collect();
        let b: Vec<char> = b.chars().collect();
        let mut queue = VecDeque::new();
        let mut visited = HashSet::new();
        visited.insert(a.clone());
        queue.push_back(a);
        let mut res = 0;
        while !queue.is_empty() {
            'outer: for _ in 0..queue.len() {
                let mut front = queue.pop_front().unwrap();
                let mut i = 0;
                while i < n && front[i] == b[i] {
                    i += 1;
                }
                if i == n {
                    return res;
                } else {
                    for j in i + 1..n {
                        if front[j] == b[i] && front[i] == b[j] {
                            front.swap(i, j);
                            if visited.insert(front.clone()) {
                                queue.push_back(front.clone());
                            }
                            front.swap(i, j);
                            continue 'outer;
                        }
                    }
                    for j in i + 1..n {
                        if front[j] == b[i] {
                            front.swap(i, j);
                            if visited.insert(front.clone()) {
                                queue.push_back(front.clone());
                            }
                            front.swap(i, j);
                        }
                    }
                }
            }
            res += 1;
        }
        0
    }
}

#[test]
fn test() {
    let a = "ab".to_string();
    let b = "ba".to_string();
    let res = 1;
    assert_eq!(Solution::k_similarity(a, b), res);
    let a = "abc".to_string();
    let b = "bca".to_string();
    let res = 2;
    assert_eq!(Solution::k_similarity(a, b), res);
    let a = "abac".to_string();
    let b = "baca".to_string();
    let res = 2;
    assert_eq!(Solution::k_similarity(a, b), res);
    let a = "aabc".to_string();
    let b = "abca".to_string();
    let res = 2;
    assert_eq!(Solution::k_similarity(a, b), res);
}