1657. Determine if Two Strings Are Close
Description
Two strings are considered close if you can attain one from the other using the following operations:
- Operation 1: Swap any two existing characters.
<ul> <li>For example, <code>a<u>b</u>cd<u>e</u> -> a<u>e</u>cd<u>b</u></code></li> </ul> </li> <li>Operation 2: Transform <strong>every</strong> occurrence of one <strong>existing</strong> character into another <strong>existing</strong> character, and do the same with the other character. <ul> <li>For example, <code><u>aa</u>c<u>abb</u> -> <u>bb</u>c<u>baa</u></code> (all <code>a</code>'s turn into <code>b</code>'s, and all <code>b</code>'s turn into <code>a</code>'s)</li> </ul> </li>
You can use the operations on either string as many times as necessary.
Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.
Example 1:
Input: word1 = "abc", word2 = "bca" Output: true Explanation: You can attain word2 from word1 in 2 operations. Apply Operation 1: "abc" -> "acb" Apply Operation 1: "acb" -> "bca"
Example 2:
Input: word1 = "a", word2 = "aa" Output: false Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.
Example 3:
Input: word1 = "cabbba", word2 = "abbccc" Output: true Explanation: You can attain word2 from word1 in 3 operations. Apply Operation 1: "cabbba" -> "caabbb" Apply Operation 2: "caabbb" -> "baaccc" Apply Operation 2: "baaccc" -> "abbccc"
Constraints:
1 <= word1.length, word2.length <= 105word1andword2contain only lowercase English letters.
Solutions
Solution 1: Counting + Sorting
According to the problem description, two strings are close if they meet the following two conditions simultaneously:
The strings
word1andword2must contain the same types of letters.The arrays obtained by sorting the counts of all characters in
word1andword2must be the same.
Therefore, we can first use an array or hash table to count the occurrences of each letter in word1 and word2 respectively, and then compare whether they are the same. If they are not the same, return false early.
Otherwise, we sort the corresponding counts, and then compare whether the counts at the corresponding positions are the same. If they are not the same, return false.
At the end of the traversal, return true.
The time complexity is $O(m + n + C \times \log C)$, and the space complexity is $O(C)$. Here, $m$ and $n$ are the lengths of the strings word1 and word2 respectively, and $C$ is the number of letter types. In this problem, $C=26$.
Python3
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
cnt1, cnt2 = Counter(word1), Counter(word2)
return sorted(cnt1.values()) == sorted(cnt2.values()) and set(
cnt1.keys()
) == set(cnt2.keys())
Java
class Solution {
public boolean closeStrings(String word1, String word2) {
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for (int i = 0; i < word1.length(); ++i) {
++cnt1[word1.charAt(i) - 'a'];
}
for (int i = 0; i < word2.length(); ++i) {
++cnt2[word2.charAt(i) - 'a'];
}
for (int i = 0; i < 26; ++i) {
if ((cnt1[i] == 0) != (cnt2[i] == 0)) {
return false;
}
}
Arrays.sort(cnt1);
Arrays.sort(cnt2);
return Arrays.equals(cnt1, cnt2);
}
}
C++
class Solution {
public:
bool closeStrings(string word1, string word2) {
int cnt1[26]{};
int cnt2[26]{};
for (char& c : word1) {
++cnt1[c - 'a'];
}
for (char& c : word2) {
++cnt2[c - 'a'];
}
for (int i = 0; i < 26; ++i) {
if ((cnt1[i] == 0) != (cnt2[i] == 0)) {
return false;
}
}
sort(cnt1, cnt1 + 26);
sort(cnt2, cnt2 + 26);
return equal(cnt1, cnt1 + 26, cnt2);
}
};
Go
func closeStrings(word1 string, word2 string) bool {
cnt1 := make([]int, 26)
cnt2 := make([]int, 26)
for _, c := range word1 {
cnt1[c-'a']++
}
for _, c := range word2 {
cnt2[c-'a']++
}
if !slices.EqualFunc(cnt1, cnt2, func(v1, v2 int) bool { return (v1 == 0) == (v2 == 0) }) {
return false
}
sort.Ints(cnt1)
sort.Ints(cnt2)
return slices.Equal(cnt1, cnt2)
}
TypeScript
function closeStrings(word1: string, word2: string): boolean {
const cnt1 = Array(26).fill(0);
const cnt2 = Array(26).fill(0);
for (const c of word1) {
++cnt1[c.charCodeAt(0) - 'a'.charCodeAt(0)];
}
for (const c of word2) {
++cnt2[c.charCodeAt(0) - 'a'.charCodeAt(0)];
}
for (let i = 0; i < 26; ++i) {
if ((cnt1[i] === 0) !== (cnt2[i] === 0)) {
return false;
}
}
cnt1.sort((a, b) => a - b);
cnt2.sort((a, b) => a - b);
return cnt1.join('.') === cnt2.join('.');
}
Rust
impl Solution {
pub fn close_strings(word1: String, word2: String) -> bool {
let mut cnt1 = vec![0; 26];
let mut cnt2 = vec![0; 26];
for c in word1.chars() {
cnt1[((c as u8) - b'a') as usize] += 1;
}
for c in word2.chars() {
cnt2[((c as u8) - b'a') as usize] += 1;
}
for i in 0..26 {
if (cnt1[i] == 0) != (cnt2[i] == 0) {
return false;
}
}
cnt1.sort();
cnt2.sort();
cnt1 == cnt2
}
}