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"
Example 4:
Input: word1 = "cabbba", word2 = "aabbss" Output: false Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.
Constraints:
1 <= word1.length, word2.length <= 105
word1
andword2
contain only lowercase English letters.
Solution: Hashtable
Two strings are close:
1. Have the same length, ccabbb => 6 == aabccc => 6
2. Have the same char set, ccabbb => (a, b, c) == aabccc => (a, b, c)
3. Have the same sorted char counts ccabbb => (1, 2, 3) == aabccc => (1, 2, 3)
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: bool closeStrings(string word1, string word2) { const int l1 = word1.length(); const int l2 = word2.length(); if (l1 != l2) return false; vector<int> f1(128), f2(128); vector<int> s1(128), s2(128); for (char c: word1) ++f1[c], s1[c] = 1; for (char c: word2) ++f2[c], s2[c] = 1; sort(begin(f1), end(f1)); sort(begin(f2), end(f2)); return f1 == f2 && s1 == s2; } }; |
Python3
1 2 3 4 5 6 7 |
# Author: Huahua class Solution: def closeStrings(self, word1: str, word2: str) -> bool: c1, c2 = Counter(word1), Counter(word2) return all([len(word1) == len(word2), c1.keys() == c2.keys(), sorted(c1.values()) == sorted(c2.values())]) |