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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

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. 😉😃💗