Determine If Two Strings Are Close

1657. 确定两个字符串是否接近

分析

长度检查：
- 如果 word1 和 word2 的长度不同，则它们无法接近，直接返回 false
字符集合一致性检查：
- 两个字符串需要包含相同的字符集合。例如，word1 = "abc" 和 word2 = "bca" 包含的字符都是 {a, b, c}，可以进行字符交换；而 word1 = "abc" 和 word2 = "bcd" 的字符集合不同，不可能接近
频次匹配：
- 统计每个字符串中字符的频次，并将频次排序。若两个字符串的字符频次分布相同，则可以通过变换使其互相接近

时间复杂度

统计字符频次的时间为 O(n)，其中 n 是字符串的长度
排序频次数组的时间为 O(26log26)，常数级别可视为 O(1)

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 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


class Solution {
public:
    bool closeStrings(string word1, string word2)
    {
        // 如果长度不同，直接返回 false
        if (word1.size() != word2.size())
            return false;

        // 统计两个字符串中每个字符的频次
        std::vector<int> cnt1(26, 0);
        std::vector<int> cnt2(26, 0);
        for (int i = 0; i < word1.size(); ++i)
        {
            ++cnt1[word1[i] - 'a'];
            ++cnt2[word2[i] - 'a'];
        }

        // 检查两个字符串是否包含相同的字符集合
        for (int i = 0; i < 26; ++i)
        {
            if ((cnt1[i] && !cnt2[i]) || (!cnt1[i] && cnt2[i]))
                return false;
        }

        // 对频次数组排序并检查是否相同
        std::sort(cnt1.begin(), cnt1.end());
        std::sort(cnt2.begin(), cnt2.end());

        return cnt1 == cnt2;
    }
};