RUST GYM Leetcode 854 K-Similar Strings Rust Solution

854. K-Similar Strings

Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.

Given two anagrams A and B, return the smallest K for which A and B are K-similar.

Example 1:

Input: A = "ab", B = "ba"
Output: 1

Example 2:

Input: A = "abc", B = "bca"
Output: 2

Example 3:

Input: A = "abac", B = "baca"
Output: 2

Example 4:

Input: A = "aabc", B = "abca"
Output: 2

Note:

1 <= A.length == B.length <= 20
A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

Rust Solution

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);
}

Having problems with this solution? Click here to submit an issue on github.