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 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day14 Java中的泛型初探

  泛型是一个很有意思也很重要的概念,本篇将简单介绍Java中的泛型特性,主要从以下角度讲解:   1.什么是泛型。   2.如何使用泛型。   3.泛型的好处...

3286
来自专栏pydata

sort algorithm

选择排序: 5(前) 8 5(后) 2 9 –> 2 8 5(后) 5(前) 9 快速排序: 5 3(前) 3(中) 4 3(后) 8 9 10 ...

892
来自专栏用户2442861的专栏

python 中迭代多个序列

http://blog.csdn.net/he_jian1/article/details/40819407

672
来自专栏程序员的知识天地

Python里面这些点,据说80%的新手都会一脸懵逼

Python虽然语法简单,通俗易懂,但是再简单它也是一门语言,就像一棵大树,总有一些树枝是弯弯绕绕的,让新手看完之后一脸懵逼,今天我们就来说说这几个点,反正我学...

773
来自专栏java一日一条

如何读懂并写出装逼的函数式代码

今天在微博上看到了 有人分享了下面的这段函数式代码,我把代码贴到下面,不过我对原来的代码略有改动,对于函数式的版本,咋一看,的确令人非常费解,仔细看一下,你可能...

642
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 三、函数

3317
来自专栏互联网开发者交流社区

面向对象的Java实现

1-1:封装 a.为什么需要封装(封装可以是数据方便维护、增加实用性、方便扩展等等。通过面向对象的思想,模拟现实生活中的事物。) b.什么是封装(封装就是将...

811
来自专栏chenjx85的技术专栏

leetcode-91-解码方法(动态规划和递归两种解法)

1、这道题给定一个字符串,字符串中只含有数字,数字1可以解码为A,数字2可以解码为B……数字26可以解码为Z。

3184
来自专栏极客猴

Python 正则表达式

我们能够使用 urllib 向网页请求并获取其网页数据。但是抓取信息数据量比较大,我们可能需要其中一小部分数据。对付刚才的难题,就需要正则表达式出马了。正则表达...

972
来自专栏鸿的学习笔记

从Scala和Python的“shell”说起

在《写给Python和Scala的碎碎念》的系列的开篇,让我们从最简单的交互式“shell”开始,一步步来看看Python和Scala的对于同一件...

1022

扫码关注云+社区

领取腾讯云代金券