LeetCode-确定两个字符串是否接近-题解

「这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战」

题目要求

题目描述

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：

操作 1：交换任意两个 现有 字符。
例如，abcde -> aecdb

操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。

示例

示例 1

输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"
复制代码

示例 2

输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
复制代码

示例 3

输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"
复制代码

示例 4

输入：word1 = "cabbba", word2 = "aabbss"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
复制代码

解题思路

仔细阅读题目，我们可以从可选的操作中获取两个信息：

• 操作一：根据操作一，字符的顺序可以任意调换，因此可以得到，如果两个字符串的字符分布是一样的，那么不论其字符顺序如何，都可以说这两个字符串接近。因为如果其字符顺序不一样，也可以通过操作一将其调整至一样。
• 操作二：根据操作二，结合操作一，如果两个字符串长度一样，且字符数目的分布也一样，那么则可以称这两个字符串接近。

综上所述，如果两个字符串满足如下两个条件，则可以称它们接近。

• 包含的字符种类完全一样
• 把各个字符的重复次数放在一个数组里，数组在排序后完全一样

代码

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        int len = word1.length();
        if(len != word2.length()) return false;
        
        vector<int> tmp1(26, 0);
        vector<int> tmp2(26, 0);
        string a = "a";

        for(int i=0; i<len; i++){
            tmp1[word1[i]-a[0]] += 1;
            tmp2[word2[i]-a[0]] += 1;
        }

        bool flag = true;
        for(int i=0; i<26; i++){
            if((tmp1[i]==0 && tmp2[i]!=0) || (tmp1[i]==0 && tmp2[i]!=0)){
                return false;
            }
        }

        sort(tmp1.begin(), tmp1.end());
        sort(tmp2.begin(), tmp2.end());

        for(int i=0; i<26; i++){
            if(tmp1[i] != tmp2[i]){
                flag = false;
                break;
            }
        }
        return flag;
    }
};
复制代码