题目 #
You are given two 0-indexed strings word1 and word2.
A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].
Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.
Example 1:
Input: word1 = "ac", word2 = "b"
Output: false
Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.
Example 2:
Input: word1 = "abcc", word2 = "aab"
Output: true
Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.
Example 3:
Input: word1 = "abcde", word2 = "fghij"
Output: true
Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.
Constraints:
- $1 <= word1.length, word2.length <= 10^5$
- word1 and word2 consist of only lowercase English letters.
思路1 统计加各种情况枚举 #
分析 #
- 自己想得，其实想复杂了，具体看注释吧
代码 #
1func abs(a int) int {
2 if a < 0 {
3 return -a
4 }
5 return a
6}
7
8func isItPossible(word1 string, word2 string) bool {
9 set1 := make(map[byte]int)
10 set2 := make(map[byte]int)
11 for _, t := range word1 {
12 v := byte(t)
13 if set1[v] > 0 {
14 set1[v]++
15 } else {
16 set1[v] = 1
17 }
18 }
19 for _, t := range word2 {
20 v := byte(t)
21 if set2[v] > 0 {
22 set2[v]++
23 } else {
24 set2[v] = 1
25 }
26 }
27
28 // 两个字符串中不同字符个数相等直接返回成功
29 diff := abs(len(set1) - len(set2))
30 more, less := set1, set2
31 if len(set1) < len(set2) {
32 more, less = set2, set1
33 }
34 if diff == 0 {
35 // 多不变少不变，多的和少的有相同的
36 // 多的和少的各有一个只有一个但对方没有的
37 // 多加少加 多的和少的各有一个有两个的
38 for k := range more {
39 if less[k] > 0 {
40 return true
41 }
42 if more[k] >= 2 {
43 for k1 := range less {
44 if less[k1] >= 2 {
45 return true
46 }
47 }
48 } else if more[k] == 1 && less[k] == 0 {
49 for k1 := range less {
50 if less[k1] == 1 && more[k1] == 0 {
51 return true
52 }
53 }
54 }
55 }
56 return false
57 }
58 if diff == 1 {
59 // 多减少不变，多的要替换的只有1个的并且替换来的是替换后已经有的
60 // 少的要替换的是有2个的并且替换来的是已经有的
61 // 多减少动了一下还是没变，多的要替换的只有1个的并且替换来的是替换后已经有的
62 // 少的要替换的是有1个的并且替换来的是少的没有的
63 // 多不变少加，多的要替换的是有2个的并且替换来的是已经有的
64 // 少的要替换的是有2个的并且替换来的是没有的
65 // 多变了一下但还是没变少加，多的要替换的是只有1个的并且是少的没有的，少的替换过来的是有两个的也是多的没有的
66 for k := range less {
67 if less[k] >= 2 && more[k] > 0 {
68 for k1 := range more {
69 if more[k1] == 1 && less[k1] > 0 && k1 != k {
70 return true
71 }
72 if more[k1] >= 2 && less[k1] == 0 {
73 return true
74 }
75 }
76 }
77 if less[k] >= 2 && more[k] == 0 {
78 for k1 := range more {
79 if more[k1] == 1 && less[k1] == 0 {
80 return true
81 }
82 }
83 }
84 if less[k] == 1 && more[k] > 0 {
85 for k1 := range more {
86 if k != k1 && more[k1] == 1 && less[k1] == 0 {
87 return true
88 }
89 }
90 }
91 }
92 return false
93 }
94 if diff == 2 {
95 // 多减少加，多的要替换的是只有1个的并且替换来的是替换后已经有的
96 // 少的要替换的是有2个的并且替换来的是没有的
97 for k := range more {
98 if more[k] == 1 && less[k] == 0 {
99 for k1 := range less {
100 if less[k1] >= 2 && more[k1] > 0 && k1 != k {
101 return true
102 }
103 }
104 }
105 }
106 return false
107 }
108 return false
109}
思路2 和上面思路一样，只不过换了遍历方式 #
分析 #
- 第一步统计少不了
- 第二步判断是否不可行也少不了
- 第三步遍历所有的交换可能，有一种满足就返回
代码 #
1func isItPossible1(word1 string, word2 string) bool {
2 set1 := make(map[rune]int)
3 set2 := make(map[rune]int)
4 for _, t := range word1 {
5 set1[t]++
6 }
7 for _, t := range word2 {
8 set2[t]++
9 }
10
11 diff := len(set1) - len(set2)
12 if diff > 2 || diff < -2 {
13 return false
14 }
15
16 getInt := func(x bool) int {
17 if x {
18 return 1
19 }
20 return 0
21 }
22
23 for k1, c1 := range set1 {
24 for k2, c2 := range set2 {
25 if k1 == k2 {
26 // 相等，交换不改变，那么长度差为0就可以
27 if diff == 0 {
28 return true
29 }
30 } else {
31 // 不相等，交换会变化，变化后相等即可
32 // 当前长度 - k1是否唯一 + k2是否存在
33 if (len(set1) - getInt(c1 == 1) + getInt(set1[k2] == 0)) == (len(set2) - getInt(c2 == 1) + getInt(set2[k1] == 0)) {
34 return true
35 }
36 }
37 }
38 }
39 return false
40}