[Leetcode][859. 亲密字符串] 简单的字符串模拟

By Long Luo

Leetcode 859. 亲密字符串

方法一:模拟

思路与算法:

虽然这个题目很简单,根据题意,但需要考虑一些边界情况:

  1. 如果字符串长度不一致,很明显不是亲密字符串;
  2. 如果字符串长度\(len < 2\),不是亲密字符串;
  3. 如果两个字符串一摸一样,但是必须更换位置,此时合法的情况只能交换两个一样的字母,意味着有字母至少出现两次;
  4. 一般情况,我们找到两个字符串字符不同的位置,但不能多于两个,同时他们可以互换。

那么针对这两种情况:

  1. 字符串不相同:遍历比较两个串,记录下不同的位置,判断这两个位置是不是正好满足互换关系即可。如果有超过两个不同的位置可以直接返回false。

  2. 字符串相同:遍历字符串,对每个字母计数;如果两个串没有不同的地方,必须有字母在字符串中出现不止一次。

代码如下所示:

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
38
public boolean buddyStrings(String s, String goal) {
if (s == null || goal == null || s.length() <= 1 || goal.length() <= 1
|| s.length() != goal.length()) {
return false;
}

int len = s.length();
int first = -1;
int second = -1;
if (s.equals(goal)) {
int[] count = new int[26];
for (int i = 0; i < len; i++) {
count[s.charAt(i) - 'a']++;
if (count[s.charAt(i) - 'a'] > 1) {
return true;
}
}
return false;
} else {
for (int i = 0; i < len; i++) {
if (s.charAt(i) != goal.charAt(i)) {
if (first == -1) {
first = i;
} else if (second == -1) {
second = i;
} else {
return false;
}
}
}
}

if (first != second && first >= 0 && second >= 0 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first)) {
return true;
}

return false;
}

也可以另外一种写法:

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
bool buddyStrings(string s, string goal) {
int lenSrc = s.length();
int lenGoal = goal.length();
if (lenSrc != lenGoal || lenSrc <= 1) {
return false;
}

vector<char> cntSrc(26);
vector<char> cntGoal(26);
int diffCnt = 0;
for (int i = 0; i < lenSrc; i++) {
int chSrc = s.at(i) - 'a';
int chGoal = goal.at(i) - 'a';
cntSrc[chSrc]++;
cntGoal[chGoal]++;
if (chSrc != chGoal) {
diffCnt++;
}
}

bool isSame = false;
for (int i = 0; i < 26; i++) {
if (cntSrc[i] != cntGoal[i]) {
return false;
}

if (cntSrc[i] > 1) {
isSame = true;
}
}

return diffCnt == 2 || (diffCnt == 0 && isSame);
}

复杂度分析

  • 时间复杂度:\(O(N)\),其中\(N\)为字符串的长度。

  • 空间复杂度:\(O(C)\),需要常数个空间保存字符串的字符统计次数,我们统计所有小写字母的个数,因此\(C = 26\)


All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗