leetcode.5603. 确定两个字符串是否接近(determine-if-two-strings-are-close)

比眉伴天荒 2022-12-21 11:57 85阅读 0赞

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

## 思路 ##

因为两种操作都不会产生新的字符，也不会使字符串长度发生变化，所以，如果两个字符串是相近的，那么两者比如符合两个要求：

*  两者的长度相同。
 *  两者包含的字符种类相同。

又因为，第二种操作可以**使两种字符的数量发生交换**，所以两个字符串还应满足下述需求：

*  把两个字符串的**字符出现次数**分别放在两个数组中，**两个数组在排序后完全一样**。

##### **「时间复杂度」** #####

*  统计字符的种类和出现次数，可以使用长度为26的数组进行哈希。`该步骤的时间复杂度为 O(n)，n 为字符串长度`。
 *  对字符数组排序的时间复杂度为 O(log(length)), length 为哈希数组的长度。

因为排序的时间复杂度是一个常数，所以整体的时间复杂度为 O(n)。

## 代码 ##

class Solution { 
    public:
        bool closeStrings(string word1, string word2) { 
            if (word1.size() != word2.size()) { 
                return false;
            }
            int arr[2][26] = {  0 }; // 统计字符出现次数
            int mar[2][26] = {  0 }; // 统计字符种类
            for (int i = 0; i < word1.size(); i++) { 
                arr[0][word1[i] - 'a']++;
                arr[1][word2[i] - 'a']++;
                mar[0][word1[i] - 'a'] = 1;
                mar[1][word2[i] - 'a'] = 1;
            }
    
            //"cabbba"
            //"abbccc"
    
            sort(arr[0], arr[0] + 26);
            sort(arr[1], arr[1] + 26);
    
            for (int i = 0; i < 26; i++) { 
                if (arr[0][i] != arr[1][i]) { 
                    return false;
                }
            }
    
            for (int i = 0; i < 26; i++) { 
                if (mar[0][i] != mar[1][i]) { 
                    return false;
                }
            }
    
            return true;
        }
    };

来自[LeetCode 第 215 场周赛 解题报告][LeetCode _ 215 _]

[LeetCode _ 215 _]: https://mp.weixin.qq.com/s/BiEjOaR_I79yOes3RNlKuQ