字符串比较-面试题

这是近几天在LintCode上遇到的一道题，题目如下：

比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是大写字母:

给出 A = "ABCD" B = "AABC"， 返回 false

给出 A = "ABCD" B = "ACD"，返回 true

• 一开始的思路是用A的每一位去和B的每一位去比较。
  如果说B每一位都能在A中找到的话，则A中包含B。
  代码如下：
  bool compareStrings(string A, string B) {
  int countA = A.length();
  int countB = B.length();
  int sub = 0;
  int temp[countB];
  for (int i = 0; i < countB; i++) {
  temp[i]=0;
  }
  for (int i = 0; i < countA; i++) {
  for (int n = 0; n < countB; n++) {
  if ( A[i] == B[n]) {
  temp[n] = 1;
  }
  }
  }
  for (int i = 0; i < countB; i++) {
  sub = temp[i] + sub;
  }
  if (sub == countB)
  return true;
  else
  return false;
  }

但是在遇到B的字符里有A的重复个的时候：
"ABCDEFG", "ACC"
A的同一个C会在B中判断两次，导致输出的结果为true，但其实应该为false。

• 所以这次改进代码，避免一个字符的多次判定。
  要做的很简单，在判定存在的语句后面加上一个break。

   for (int i = 0; i < countA; i++) {
       for (int n = 0; n < countB; n++) {
           if ( A[i] == B[n]) {
           temp[n] = 1;
           break;
           }
       }
   }
  

就像上面提到的情况，问题又出现了：
"AAAAAAAAAAAABBBBBCDD", "ABCDD"（true）
A的DD在B中只判定了B的第一个D，就跳出了，所以输出为false。

• ……很无奈接着补充代码：

   for (int i = 0; i < countA; i++) {
       for (int n = 0; n < countB; n++) {
           if ( A[i] == B[n]) {
           temp[n] = 1;
           if ( A[i] != A[i-1])//当A的后一个字符与前一个不一样时才跳出循环
           break;
           }
       }
   }
  

好吧，糟糕的情况又出现了。
"AAAAAAAAAAAAAAAAAAABBBBBBBBBDFADSFJALSDJFALSDJFSADFADF", "AAAAAABBBBBBBBBDFJALDJF"（true）
这里又错误的返回了一个fasle，由于A中的D并不是连续，所以和上面的错误类似，B中的第二个D不能得到判定。
做到这里就不得不说下了，像你已经看到这种修修补补的代码，一般情况下都是很糟糕的，而且问题较多。因为必须要顺着前面的思路，来解决后面的问题 ，你很有可能发现之前的算法结构在解决后面出现问题时是异常困难的。最好构造算法之前就要考虑到最坏的情况，或者说最后重构下自己的代码。
由于我一开始看到题目中给的的数据很简单就没考虑到现在的情况。
我觉得我的方法需要换一种了。

思路如下：

• 统计两边的信息进行比较。如果B中的每种字符的个数小于等于A中的，则A包含B。
  代码如下：
  int Achar[26];//储存字符串的每个字母个数
  int Bchar[26];
  for (int i = 0; i<26; i++) {
  Achar[i] = 0;
  Bchar[i] = 0;
  }
  int Adate,Bdate;//记录AB的字符统计数据
  int countA = A.length();
  int countB = B.length();
  for (int i = 0; i<countA; i++) {
  int index;
  index = A[i] - 65;
  Achar[index]++;
  }
  for (int i = 0; i<countB; i++) {
  int index;
  index = B[i] - 65;//65为大写A的ASCⅡ码值
  Bchar[index]++;
  }
  for (int i = 0; i<26; i++) {
  if (Achar[i]<Bchar[i])
  return false;
  }
  return true;
  }

这一次19个测试数据全部通过。😄