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
andB
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.