Compare Strings

Question

• lintcode: (55) Compare Strings

  1. Compare two strings A and B, determine whether A contains all of the characters in B.
     2. 3. The characters in string A and B are all Upper Case letters.
     3. 5. Example
     4. For A = "ABCD", B = "ABC", return true.
     5. 8. For A = "ABCD" B = "AABC", return false.

題解

題 Two Strings Are Anagrams | Data Structure and Algorithm 的變形題。題目意思是問B中的所有字元是否都在A中，而不是單個字元。比如B=”AABC”包含兩個「A」，而A=”ABCD”只包含一個「A」，故返回false. 做題時注意題意，必要時可向面試官確認。
既然不是類似 strstr 那樣的匹配，直接使用二重循環就不太合適了。題目中另外給的條件則是A和B都是全大寫單字，理解題意後容易想到的方案就是先遍歷 A 和 B 統計各字元出現的次數，然後比較次數大小即可。嗯，祭出萬能的哈希表。

C++

  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.         if (A.size() < B.size()) {
    11.             return false;
    12.         }
    13.   14.         const int AlphabetNum = 26;
    15.         int letterCount[AlphabetNum] = {0};
    16.         for (int i = 0; i != A.size(); ++i) {
    17.             ++letterCount[A[i] - 'A'];
    18.         }
    19.         for (int i = 0; i != B.size(); ++i) {
    20.             --letterCount[B[i] - 'A'];
    21.             if (letterCount[B[i] - 'A'] < 0) {
    22.                 return false;
    23.             }
    24.         }
    25.   26.         return true;
    27.     }
    28. };

源碼解析

1. 異常處理，B 的長度大於 A 時必定返回false, 包含了空串的特殊情況。
2. 使用額外的輔助空間，統計各字元的頻次。

複雜度分析

遍歷一次 A 字串，遍歷一次 B 字串，時間複雜度最壞 O(2n), 空間複雜度為 O(26).