首页 > [容易]比较字符串

[容易]比较字符串

题目来源：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)
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)
22         {
23             for(int j=0;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)
12             ++counts[(A[i]-'A')];
13         for(int j=0;j)
14         {
15             if(--counts[(B[j]-'A')]<0)
16                 return false;
17         }
18         return true;
19     }
20 };

转载于:https://www.cnblogs.com/hslzju/p/5491463.html

更多相关：

©2024 11GX.COM