1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public boolean closeStrings(String word1, String word2) {
if (word1.length() != word2.length()) {
return false;
}
Map<Character, Integer> letterCountWord1 = new TreeMap<>();
Map<Character, Integer> letterCountWord2 = new TreeMap<>();
for (char letter : word1.toCharArray()) {
letterCountWord1.put(letter, letterCountWord1.getOrDefault(letter, 0) + 1);
}
for (char letter : word2.toCharArray()) {
letterCountWord2.put(letter, letterCountWord2.getOrDefault(letter, 0) + 1);
}
List<Character> word1LetterList = new ArrayList<>(letterCountWord1.keySet());
List<Character> word2LetterList = new ArrayList<>(letterCountWord2.keySet());
if (word1LetterList.size() != word2LetterList.size()) {
return false;
}
Collections.sort(word1LetterList);
Collections.sort(word2LetterList);
for (int i = 0; i < word1LetterList.size(); i++) {
if (word1LetterList.get(i) != word2LetterList.get(i)) {
return false;
}
}
List<Integer> word1Freq = new ArrayList<>(letterCountWord1.values());
List<Integer> word2Freq = new ArrayList<>(letterCountWord2.values());
Collections.sort(word1Freq);
Collections.sort(word2Freq);
for (int i = 0; i < word1Freq.size(); i++) {
if (!word1Freq.get(i).equals(word2Freq.get(i))) {
return false;
}
}
return true;
}
}
|
这道题的思路是两个word的character set的要一样(每个word中unique character是一样的). 同时计算每个character出现的频率. 这些频率构成的list也要一样. 也就是word1的频率list中的每个元素在word2的频率list都有对应相等的值.
第一种交换本质是这样的. 比如:
a: 5
b: 3
a出现5次, b出现3次. 一交换变成这样:
a: 3
b: 5
那其实第一种操作就是交换频率. 如果两个word的character set相同, 同时频率list也相同, 那通过适当的交换可以让两个word的每个character的出现频率是一一对应一样的. 然后我们再通过第二个操作让实际的两个word每个位置的character一一对应相等即可.
时间复杂度: O(nlogn)
空间复杂度: O(n)
