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.
- For example,
abcde -> aecdb
- For example,
- Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
- For example,
aacabb -> bbcbaa
(alla
's turn intob
's, and allb
's turn intoa
's)
- For example,
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 <= 105
word1
andword2
contain 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
word1
andword2
must contain the same types of letters. - The arrays obtained by sorting the counts of all characters in
word1
andword2
must 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$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|