# 字符串包含 ## 題目描述 給定兩個分別由字母組成的字符串A和字符串B，字符串B的長度比字符串A短。請問，如何最快地判斷字符串B中所有字母是否都在字符串A里？ 為了簡單起見，我們規定輸入的字符串只包含大寫英文字母，請實現函數bool StringContains(string &A, string &B) 比如，如果是下面兩個字符串： String 1：ABCD String 2：BAD 答案是true，即String2里的字母在String1里也都有，或者說String2是String1的真子集。 如果是下面兩個字符串： String 1：ABCD String 2：BCE 答案是false，因為字符串String2里的E字母不在字符串String1里。 同時，如果string1：ABCD，string 2：AA，同樣返回true。 ## 分析與解法 題目描述雖長，但題意很明了，就是給定一長一短的兩個字符串A，B，假設A長B短，要求判斷B是否包含在字符串A中。 初看似乎簡單，但實現起來并不輕松，且如果面試官步步緊逼，一個一個否決你能想到的方法，要你給出更好、最好的方案時，恐怕就要傷不少腦筋了。 ### 解法一 判斷string2中的字符是否在string1中?最直觀也是最簡單的思路是，針對string2中每一個字符，逐個與string1中每個字符比較，看它是否在String1中。 代碼可如下編寫： ```cpp bool StringContain(string &a,string &b) { for (int i = 0; i < b.length(); ++i) { int j; for (j = 0; (j < a.length()) && (a[j] != b[i]); ++j) ; if (j >= a.length()) { return false; } } return true; } ``` 假設n是字符串String1的長度，m是字符串String2的長度，那么此算法，需要O(n*m)次操作。顯然，時間開銷太大，應該找到一種更好的辦法。 ### 解法二 如果允許排序的話，我們可以考慮下排序。比如可先對這兩個字符串的字母進行排序，然后再同時對兩個字串依次輪詢。兩個字串的排序需要(常規情況)O(m log m) + O(n log n)次操作，之后的線性掃描需要O(m+n)次操作。 關于排序方法，可采用最常用的快速排序，參考代碼如下： ```cpp //注意A B中可能包含重復字符，所以注意A下標不要輕易移動。這種方法改變了字符串。如不想改變請自己復制 bool StringContain(string &a,string &b) { sort(a.begin(),a.end()); sort(b.begin(),b.end()); for (int pa = 0, pb = 0; pb < b.length();) { while ((pa < a.length()) && (a[pa] < b[pb])) { ++pa; } if ((pa >= a.length()) || (a[pa] > b[pb])) { return false; } //a[pa] == b[pb] ++pb; } return true; } ``` ### 解法三 有沒有比快速排序更好的方法呢？ 我們換一種角度思考本問題： 假設有一個僅由字母組成字串，讓每個字母與一個素數對應，從2開始，往后類推，A對應2，B對應3，C對應5，......。遍歷第一個字串，把每個字母對應素數相乘。最終會得到一個整數。 利用上面字母和素數的對應關系，對應第二個字符串中的字母，然后輪詢，用每個字母對應的素數除前面得到的整數。如果結果有余數，說明結果為false。如果整個過程中沒有余數，則說明第二個字符串是第一個的子集了（判斷是不是真子集，可以比較兩個字符串對應的素數乘積，若相等則不是真子集）。 思路總結如下： 1. 按照從小到大的順序，用26個素數分別與字符'A'到'Z'一一對應。 2. 遍歷長字符串，求得每個字符對應素數的乘積。 3. 遍歷短字符串，判斷乘積能否被短字符串中的字符對應的素數整除。 4. 輸出結果。 如前所述，算法的時間復雜度為O(m+n)的最好的情況為O(n)（遍歷短的字符串的第一個數，與長字符串素數的乘積相除，即出現余數，便可退出程序，返回false），n為長字串的長度，空間復雜度為O(1)。 ```cpp //此方法只有理論意義，因為整數乘積很大，有溢出風險 bool StringContain(string &a,string &b) { const int p[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79, 83, 89, 97, 101}; int f = 1; for (int i = 0; i < a.length(); ++i) { int x = p[a[i] - 'A']; if (f % x) { f *= x; } } for (int i = 0; i < b.length(); ++i) { int x = p[b[i] - 'A']; if (f % x) { return false; } } return true; } ``` 此種素數相乘的方法看似完美，但缺點是素數相乘的結果容易導致整數溢出。 ### 解法四 如果面試官繼續追問，還有沒有更好的辦法呢？計數排序？除了計數排序呢？ 事實上，可以先把長字符串a中的所有字符都放入一個Hashtable里，然后輪詢短字符串b，看短字符串b的每個字符是否都在Hashtable里，如果都存在，說明長字符串a包含短字符串b，否則，說明不包含。 再進一步，我們可以對字符串A，用位運算（26bit整數表示)計算出一個“簽名”，再用B中的字符到A里面進行查找。 ```cpp // “最好的方法”，時間復雜度O(n + m)，空間復雜度O(1) bool StringContain(string &a,string &b) { int hash = 0; for (int i = 0; i < a.length(); ++i) { hash |= (1 << (a[i] - 'A')); } for (int i = 0; i < b.length(); ++i) { if ((hash & (1 << (b[i] - 'A'))) == 0) { return false; } } return true; } ``` 這個方法的實質是用一個整數代替了hashtable，空間復雜度為O(1)，時間復雜度還是O(n + m)。 ## 舉一反三 1、變位詞 - 如果兩個字符串的字符一樣，但是順序不一樣，被認為是兄弟字符串，比如bad和adb即為兄弟字符串，現提供一個字符串，如何在字典中迅速找到它的兄弟字符串，請描述數據結構和查詢過程。