力扣练习之确定两个字符串是否接近

发布于:2025-03-14 ⋅ 阅读:(23) ⋅ 点赞:(0)

目录

题目:

题解:

详细题解


题目:

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

  • 操作 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"

提示:

  • 1 <= word1.length, word2.length <= 105
  • word1 和 word2 仅包含小写英文字母

题解:

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        //存储各个字符出现的频率
        vector<int> count1(26),count2(26);//因为一共就26个字母,所以长度26即可
        for(char c: word1){
            count1[c-'a']++;
        }
        for(char c: word2){
            count2[c-'a']++;
        }
        //验证是否字符一样
        for(int i=0;i<26;i++){
            if(count2[i]>0&&count1[i]==0 ||count2[i]==0&&count1[i]>0){
                return false;
            }
        }
        //字符一样之后,验证是否有相同的次数出现
        sort(count1.begin(),count1.end());
        sort(count2.begin(),count2.end());
        return count1==count2;
    }
};

详细题解

刚开始其实我看到这个题目是懵的,因为我忘了c++关于字符串的遍历还有统计啥的方法咋做了哈哈哈,所以就看了官方题解。其实我觉得官方题解非常的妙。

对于这个题我觉得理解到底什么叫两个字符串接近是关键,对于题目的两个操作其实说人话就是

1.这两个字符串出现的字符必须得一样

2. 字符的出现频次是要一样的(这里的意思不是说相同字符出现的频次必须要一样,而是说只要有跟它一样的频次的字符出现在另一个字符串里就可以)

所以在解答这个题的时候同样可以分成两部分

首先我们使用两个数组来分别存储不同字符出现的频率,其中下标来表示字符的ASCII码,元素来表示频率

//存储各个字符出现的频率
        vector<int> count1(26),count2(26);//因为一共就26个字母,所以长度26即可
        for(char c: word1){
            count1[c-'a']++;
        }
        for(char c: word2){
            count2[c-'a']++;
        }

然后可以来判断两个字符串出现的字符是否一样了 ,因为我们用下标来表示字符,元素来表示出现的次数,那么对于同样下标的如果有一个数组元素为0,那说明他对应的字符串是没有该元素的,所以也就是两个字符串中字符不一样,也就是不接近,所以也就可以直接返回false了

//验证是否字符一样
        for(int i=0;i<26;i++){
            if(count2[i]>0&&count1[i]==0 ||count2[i]==0&&count1[i]>0){
                return false;
            }
        }

通过该判断之后,我们要判断的是是否有相同频次出现,那这个时候,我们就可以进行排序,排序完看看这两个count数组是否一样即可,如果不一样,比如说count1里有5,但是count2里并没有,那么说明字符串1里有一个字符出现了5次,二字符串2里并没有出现5次的字符,这也会不符合接近的定义,所以返回false,如果完全一样,那么就返回true

 //字符一样之后,验证是否有相同的次数出现
        sort(count1.begin(),count1.end());
        sort(count2.begin(),count2.end());
        return count1==count2;

后话:希望我下次再次做这个题的时候,还能像现在这样思路清晰~


网站公告

今日签到

点亮在社区的每一天
去签到