55. 比较字符串

比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母 样例 给出 A = "ABCD" B = "ACD",返回 true 给出 A = "ABCD" B = "AABC", 返回 false 先给出一个错误思路,用这个思路竟然通过了百分之95的测试数据,好可怕,嗯,是这样的,一开始我想的是,对于B中的每一个字母,我都去A中遍历,看是否有和B中一样的(同时用一个标志位指向找到的这个位置,保证不能B中相同的两个元素找到同一个A中的同一个元素,同时统计找到的字母个数,如果全部能找到,这个个数应该是等于B.size()的),乍一想这个思路还不错,其实有一个致命的错误,先看代码:

   bool compareStrings(string &A, string &B) {
        if(A.size()!=0&&B.size()==0)
        return true;
         if(A.size()==0&&B.size()==0)
         return true;
         if(A.size()==0&&B.size()!=0)
         return false;   //先处理三种特殊情况
        int flag=-1;   //标志找到的是哪一位,主要是不能B中两个找到A中的同一位
        int sum=0;     //统计一共找到多少个,如果这个最后等与B的size,就可返回true
        for(int i=0;i<B.size();i++)  //遍历B中的字符
        {
            for(int j=0;j<A.size();j++)  //遍历A,看是否包含
            {
                if(B[i]==A[j]&&j!=flag)   //如果B中的每一个A中都能找到。且和上次的不一样
                {
                    flag=j;
                    sum++;
                    break;
                }
            }
        }
        if(sum==B.size())
        return true;
        else 
        return false;
    }

错误是什么呢?就是如果A中有相同的两个字母的话,无论B中有多少个和这个字母相同的,按照上面的思路都会判断为正确: eg:A="AABBB"; B="AAAAAA"; 这种情况的话,对于每一次B中的A来说,A中我设置的标志位都知识在0,1之间跳动(我也是换了VS调试才发现的这个问题,太大意了,那么能不能设置成每次标志位都大于上一次呢?显然对这个例子是可以的,但是考虑到B中先出现的元素可能在A中较后的位置出现:A="AB"; B="BA";这又要另外处理,还是很麻烦。遂放弃这种思路了。) 思路2:后来想到用map来做这个是有点可以的:把两个字符串分别放入两个map<char,int>里,会自动排序好,int保存各自出现的次数,然后再比较两个map对应的位置出现的次数的多少就可以了,后来发现,要同时遍历两个map并比较对应位置这个是不太好实现的。 思路3:后来再想了想,又想回去思路1中了,发现自己陷入一个自己挖的坑里,如果要保证重复搜寻的时候不搜到上次的字符,我们为什么不把这个字符去掉或者换掉呢?这样一想的话题目中限制在大写字母简直就是为了可以这么做的啊!于是:

 bool compareStrings(string &A, string &B) {
        if(A.size()!=0&&B.size()==0)
        return true;
         if(A.size()==0&&B.size()==0)
         return true;
         if(A.size()==0&&B.size()!=0)
         return false;   //先处理三种特殊情况
         int sum=0;     //统计一共找到多少个,如果这个最后等与B的size,就可返回true
        for(int i=0;i<B.size();i++)  //遍历B中的字符
        {
            for(int j=0;j<A.size();j++)  //遍历A,看是否包含
            {
                if(B[i]==A[j])   //如果找到,就把A中的这个置为0,字符串0,保证下次不会再找到这个
                {
                   
                    A[j]='0';
                    sum++;
                    break;
                }
            }
        }
        if(sum==B.size())
        return true;
        else 
        return false;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 702. 连接两个字符串中的不同字符

    连接两个字符串中的不同字符。 给出两个字符串, 你需要修改第一个字符串,将所有与第二个字符串中相同的字符删除, 并且第二个字符串中不同的字符与第一个字符串的不...

    和蔼的zhxing
  • 408. 二进制求和

    给定两个二进制字符串,返回他们的和(用二进制表示) 样例 a = 11 b = 1 返回 100 非常惭愧还不是自己想来的算法,注意到几点: 1.数...

    和蔼的zhxing
  • 133. 最长单词 一次遍历+vector容器

    如果只是要最长的一个单词,那么只需要一次遍历即可,这里是要求求出最长单词的集合,稍作改变即可。

    和蔼的zhxing
  • 短视频商城源码,制作彩色验证码

    yunbaokeji柯基
  • C语言中size_t和size_type 的区别

    1)size_tsize_t是用于数组的下标值类型,也可以用来“接收”sizeof操作符的返回值。

    ccf19881030
  • 880.Decoded String at Index

    思路 用size表示在i处,字符串进行解码后的长度。 如果有一个解码后的字符串为appleappleappleappleappleapple,且K=24,那...

    平凡的学生族
  • [开发技巧]·AdaptivePooling与Max/AvgPooling相互转换

    自适应池化Adaptive Pooling是PyTorch的一种池化层,根据1D,2D,3D以及Max与Avg可分为六种形式。

    小宋是呢
  • C 库函数 - fread()

    C 库函数 size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream) 从给定流 stre...

    心跳包
  • JS的函数调用栈有多深?

    译者按: 有时候会遇到 Maximum call stack size exceeded 的问题,本文教你 stack size 的计算方法。

    Fundebug
  • JS的函数调用栈有多深?

    译者按: 有时候会遇到 Maximum call stack size exceeded 的问题,本文教你 stack size 的计算方法。

    Fundebug

扫码关注云+社区

领取腾讯云代金券