1657. Determine if Two Strings Are Close
題目：
你可以用兩種操作
1. 隨意更換字元順序
2. 把字串內兩種符號種類對換
看能不能用他們把兩個字串變成一樣的
思路：
操作一其實沒意思 不用考慮 因為操作次數無限
重點還是操作二
操作二這樣寫
代表只要兩個字串的字元 freq 一樣
字元種類也一樣 沒有一個有一個沒有的
就可以變換
最簡單的方法
可以用 HashMap 蒐集次數
用 HashSet 比較字母
用 Vec sort 比較 freq
但這樣時間複雜度不夠高
更高的還是創 26 大小字母陣列來解
Code:
use std::collections::{HashMap, HashSet};
impl Solution {
pub fn close_strings(word1: String, word2: String) -> bool {
let mut freq1 = HashMap::new();
let mut freq2 = HashMap::new();
for c in word1.chars() {
*freq1.entry(c).or_insert(0) += 1;
}
for c in word2.chars() {
*freq2.entry(c).or_insert(0) += 1;
}
let set1: HashSet<_> = freq1.keys().cloned().collect();
let set2: HashSet<_> = freq2.keys().cloned().collect();
if set1 != set2 {
return false;
}
let mut count1: Vec<_> = freq1.values().cloned().collect();
let mut count2: Vec<_> = freq2.values().cloned().collect();
count1.sort();
count2.sort();
if count1 != count2 {
return false;
}
true
}
}
26 字元陣列版：
impl Solution {
pub fn close_strings(word1: String, word2: String) -> bool {
let mut count1 = [0; 26];
let mut count2 = [0; 26];
let mut set1 = [false; 26];
let mut set2 = [false; 26];
for c in word1.chars() {
let i = (c as u8 - b'a') as usize;
count1[i] += 1;
set1[i] = true;
}
for c in word2.chars() {
let i = (c as u8 - b'a') as usize;
count2[i] += 1;
set2[i] = true;
}
if set1 != set2 {
return false;
}
let mut freq1: Vec<_> = count1.iter()
.filter(|&&x| x > 0)
.cloned().collect();
let mut freq2: Vec<_> = count2.iter()
.filter(|&&x| x > 0)
.cloned().collect();
freq1.sort();
freq2.sort();
freq1 == freq2
}
}