Medium
,String
,Hash Table
,Sorting
1657. Determine if Two Strings Are Close
Two strings are considered close if you can attain one from the other using the following operations:
For example, abcde -> aecdb
For example, aacabb -> bbcbaa (all
a
's turn intob
's, and allb
's turn intoa
's)
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:
word1.length
, word2.length
<= 105word1
and word2
contain only lowercase English letters.
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
if len(word1) != len(word2): return False
dict1, dict2 = {}, {}
for word in word1:
dict1[word] = dict1.get(word, 0) + 1
for word in word2:
dict2[word] = dict2.get(word, 0) + 1
val1, val2 = sorted(dict1.values()), sorted(dict2.values())
return set(word1) == set(word2) and val1 == val2
Kobe Dec 2, 2022
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
def stat(word):
Q = dict()
for x in word:
if x in Q:
Q[x] += 1
else:
Q[x] = 1
amount = [ v for i,(k,v) in enumerate(Q.items())]
word_set = [ k for i,(k,v) in enumerate(Q.items())]
amount = sorted(amount)
word_set = sorted(word_set)
#print(word_set)
#print(amount)
return amount+word_set
return stat(word1) == stat(word2)
玉山 Dec 2, 2022
function closeStrings(word1, word2) {
if (word1.length !== word2.length) return false;
const map1 = new Map();
const map2 = new Map();
for (let i = 0; i < word1.length; i++) {
map1.set(word1[i], (map1.get(word1[i]) || 0) + 1);
map2.set(word2[i], (map2.get(word2[i]) || 0) + 1);
}
// 要有相同的字母
if (map1.size !== map2.size) return false;
for (const key of map1.keys()) {
if (!map2.has(key)) return false;
}
// 且字母個數分布要一樣
const arr1 = Array.from(map1.values()).sort((a, b) => a - b);
const arr2 = Array.from(map2.values()).sort((a, b) => a - b);
for (let i = 0; i < arr1.length; i++) {
if (arr1[i] !== arr2[i]) return false;
}
return true;
}
順哥:就char set要一樣,個數分布要一樣。
感謝順哥給的提示,感恩順哥讚嘆順哥。
Marsgoat Dec 2, 2022