题目来源：http://www.lintcode.com/zh-cn/problem/compare-strings/
先贴上错误代码，测试案例没有全部通过。不一定是顺序的。
1 class Solution {
2 public:
3 /**
4 * @param A: A string includes Upper Case letters
5 * @param B: A string includes Upper Case letter
6 * @return: if string A contains all of the characters in B return true
7 * else return false
8 */
9 bool compareStrings(string A, string B) {
10 // write your code here
11 int lenA=A.size();
12 int lenB=B.size();
13 int i=0,j=0,temp=0;
14 if(lenA==0&&lenB==0)
15 return true;
16 if(lenA==0)
17 return false;
18 for(;i<lenB;i++)
19 {
20 if(A[j]==B[i])
21 {
22 j++;
23 temp++;
24 }
25 else
26 {
27 while(j<lenA)
28 {
29 j++;
30 if(A[j]==B[i])
31 {
32 j++;
33 temp++;
34 break;
35 }
36 }
37 }
38 }
39 if(temp==lenB)
40 return true;
41 else
42 return false;
43 }
44 };方法一：直接法
修改之后，可以accept的程序如下：
1 class Solution {
2 public:
3 /**
4 * @param A: A string includes Upper Case letters
5 * @param B: A string includes Upper Case letter
6 * @return: if string A contains all of the characters in B return true
7 * else return false
8 */
9 bool compareStrings(string A, string B) {
10 // write your code here
11 int lenA=A.size();
12 int lenB=B.size();
13 if(lenA==0&&lenB==0)
14 return true;
15 if(lenA==0)
16 return false;
17 if(lenB==0)
18 return true;
19 int temp=0;
20 string::iterator p;
21 for(int i=0;i<B.size();i++)
22 {
23 for(int j=0;j<A.size();j++)
24 {
25 if(A[j]==B[i])
26 {
27 temp++;
28 p=A.begin()+j;
29 A.erase(p);
30 break;
31 }
32 }
33 }
34 if(temp==B.size())
35 return true;
36 else
37 return false;
38 }
39 };方法二：用数组count[26]存放A中26个字母出现的次数。对B每个字母遍历，如果A中对应位置小于0，说明找不到，返回false。
可以accept的程序2如下：
1 class Solution {
2 public:
3 /**
4 * @param A: A string includes Upper Case letters
5 * @param B: A string includes Upper Case letter
6 * @return: if string A contains all of the characters in B return true
7 * else return false
8 */
9 bool compareStrings(string A, string B) {
10 int count[26];
11 for (int i = 0; i < 26; i++) {
12 count[i] = 0;
13 }
14 for (int i = 0; i < A.length(); i++) {
15 count[A[i] - 'A'] ++;
16 }
17 for (int i = 0; i < B.length(); i++) {
18 count[B[i] - 'A'] --;
19 if (count[B[i] - 'A'] < 0) {
20 return false;
21 }
22 }
23 return true;
24 }
25 };方法三：用哈希表存放，节省空间。
可以accept的程序3如下：
1 class Solution { 2 public: 3 /** 4 * @param A: A string includes Upper Case letters 5 * @param B: A string includes Upper Case letter 6 * @return: if string A contains all of the characters in B return true 7 * else return false 8 */ 9 bool compareStrings(string A, string B) { 10 unordered_map<int, int> counts; 11 for(int i=0;i<A.size();i++) 12 ++counts[(A[i]-'A')]; 13 for(int j=0;j<B.size();j++) 14 { 15 if(--counts[(B[j]-'A')]<0) 16 return false; 17 } 18 return true; 19 } 20 };
