比较两个字符串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;
}
over
网友评论