1 算法題 ：判斷一個字符串是否包含另一個字符串的所有字符（不一定連續）

1.1 題目含義

判斷一個字符串（稱為“主字符串”或“大字符串”）是否包含另一個字符串（稱為“子字符串”或“小字符串”）的所有字符，且不論這些字符在主字符串中的順序和連續性。換句話說，我們要確認子字符串的每一個字符至少在主字符串中出現一次。

1.2 示例

示例 1:
輸入:

• 主字符串: “abcdefghijklmnopqrstuvwxyz”
• 子字符串: “abcde”

輸出: true
解釋: 主字符串包含子字符串的所有字符。

示例 2:
輸入:

• 主字符串: “mississippi”
• 子字符串: “missip”

輸出: true
解釋: 盡管 “missip” 在主字符串中不是連續的，但主字符串包含子字符串的所有字符。

示例 3:
輸入:

• 主字符串: “abcdefg”
• 子字符串: “defghijklmnop”

輸出: false
解釋: 主字符串不包含子字符串的所有字符，因為 “hijklmnop” 中的字符在主字符串中沒有出現。

2 解題思路

解題思路如下：

（1）初始化哈希表：
在 C++ 中，我們可以使用std::unordered_map來作為哈希表。首先，遍歷子字符串，對于每個字符，我們在unordered_map中增加其計數。

（2）遍歷主字符串并更新哈希表：
然后，遍歷主字符串。對于主字符串中的每個字符，我們檢查它是否在unordered_map中。如果在，則將其對應的計數減一。如果不在，說明主字符串中缺少該字符，因此可以立即返回false。

（3）檢查哈希表：
在遍歷完主字符串后，我們檢查 unordered_map 中所有字符的計數是否都已經歸零。如果所有計數都為零，說明主字符串包含了子字符串的所有字符，返回 true；如果存在任何非零計數，說明主字符串缺少某些字符，返回 false。

（4）返回結果：
根據unordered_map的狀態，返回相應的布爾值。

3 算法實現代碼

3.1 使用哈希表

如下為算法實現代碼：

#include <iostream>  
#include <unordered_map>  
#include <string>  class Solution
{
public:bool isContainsAllCharacters(const std::string& mainString, const std::string& subString) {// 初始化哈希表  std::unordered_map<char, int> charCounts;for (char c : subString) {charCounts[c]++;}// 遍歷主字符串并更新哈希表  for (char c : mainString) {if (charCounts.find(c) != charCounts.end()) {charCounts[c]--;if (charCounts[c] == 0) {// 如果字符的計數減到0，從哈希表中刪除該字符  charCounts.erase(c);}}}// 檢查哈希表  return charCounts.empty(); // 如果哈希表為空，說明所有字符都被找到了  }
};

在 isContainsAllCharacters 成員函數中，首先使用std::unordered_map<char, int>創建了一個名為charCounts的哈希表。這個哈希表將存儲 subString中 每個字符及其出現的次數（遍歷 subString 中的每個字符 c，并在 charCounts 中增加該字符的計數。如果字符 c 在 charCounts 中不存在，它會被插入到哈希表中并設置計數為 1；如果它已經存在，則計數增加 1）。

接下來，使用 find 方法來檢查字符 c 是否存在于 charCounts 中。如果字符 c 在 charCounts 中存在，將其計數減 1。如果減1后計數變為 0，說明 mainString 中的這個字符與 subString 中的字符數量相匹配，可以從 charCounts中 刪除這個字符。

最后，如果哈希表為空，說明 mainString 包含了 subString 中的所有字符，因為所有在 subString 中出現的字符都已經在 mainString 中被匹配并從哈希表中刪除了。如果哈希表不為空，則意味著至少有一個 subString 中的字符在 mainString 中沒有出現。

調用上面的算法，并得到輸出：

int main() 
{Solution solution;std::string mainString = "abcdefghijklmnopqrstuvwxyz";std::string subString = "abcde";std::cout << "Does \"" << mainString << "\" contain all characters of \"" << subString << "\"? "<< (solution.isContainsAllCharacters(mainString, subString) ? "Yes" : "No") << std::endl;mainString = "mississippi";subString = "missip";std::cout << "Does \"" << mainString << "\" contain all characters of \"" << subString << "\"? "<< (solution.isContainsAllCharacters(mainString, subString) ? "Yes" : "No") << std::endl;mainString = "abcdefg";subString = "defghijklmnop";std::cout << "Does \"" << mainString << "\" contain all characters of \"" << subString << "\"? "<< (solution.isContainsAllCharacters(mainString, subString) ? "Yes" : "No") << std::endl;return 0;
}

上面代碼的輸出為：

Does "abcdefghijklmnopqrstuvwxyz" contain all characters of "abcde"? Yes
Does "mississippi" contain all characters of "missip"? Yes
Does "abcdefg" contain all characters of "defghijklmnop"? No

3.2 使用排序和比較的方法

這種方法的思路是，如果主字符串包含子字符串的所有字符，那么對兩個字符串進行排序后，排序后的子字符串應該是排序后的主字符串的一個子序列。該方法的優點是它不需要使用額外的數據結構來記錄字符的出現次數，而是通過比較排序后的字符串來直接得出結論。然而，它的缺點是需要對字符串進行排序，這可能會增加一些計算復雜度。
如下為算法實現代碼：

#include <iostream>  
#include <cctype>  
#include <string>  
#include <algorithm> // 用于std::sortclass Solution 
{
public:bool isContainsAllCharacters(const std::string& mainString, const std::string& subString) {// 對兩個字符串進行排序std::string sorted_main = mainString;std::string sorted_sub = subString;std::sort(sorted_main.begin(), sorted_main.end());std::sort(sorted_sub.begin(), sorted_sub.end());// 使用雙指針法檢查 sorted_sub 是否是 sorted_main 的子序列  int i = 0, j = 0;while (i < sorted_sub.length() && j < sorted_main.length()) {if (sorted_sub[i] == sorted_main[j]) {i++; // 移動到 sorted_sub 的下一個字符  }j++; // 移動到 sorted_main 的下一個字符  }// 如果 sorted_sub 的所有字符都在 sorted_main 中找到，則 sorted_sub 是 sorted_main 的子序列  return  sorted_sub.length() == i;}
};

在這個實現中，首先使用 std::sort 函數對這兩個字符串進行排序。排序后，sorted_main 和 sorted_sub 分別包含與 mainString 和 subString 相同但已排序的字符。

然后，使用雙指針法檢查 sorted_sub 是否是 sorted_main 的子序列（注意：無論是否找到匹配的字符，都將 j 增加 1，以繼續檢查 sorted_main 的下一個字符）。

接著，判斷 sorted_sub 的所有字符是否都在 sorted_main 中找到（如果 sorted_sub 的所有字符都在 sorted_main 中找到，那么 i 的值應該等于 sorted_sub 的長度）。

4 測試用例

以下是針對上面算法的測試用例：

（1）基礎測試用例：
輸入：

• 主字符串: “abcdefg”
• 子字符串: “bcd”

輸出: true
解釋: 主字符串包含子字符串的所有字符。

（2）包含所有字符但順序不同：
輸入：

• 主字符串: “bacdefg”
• 子字符串: “abc”

輸出: true
解釋: 雖然字符順序不同，但主字符串包含子字符串的所有字符符。

（3）缺少一個字符：
輸入：

• 主字符串: “abdefg”
• 子字符串: “abc”

輸出: false
解釋: 主字符串缺少子字符串中的一個字符 ‘c’。

（4）包含重復字符：
輸入：

• 主字符串: “aabbbccc”
• 子字符串: “abc”

輸出: true
解釋: 即使主字符串中的字符有重復，但它仍然包含子字符串中的所有字符。

（5）子字符串是主字符串的前綴：
輸入：

• 主字符串: “abcdefg”
• 子字符串: “abc”

輸出: true
解釋: 子字符串是主字符串的前綴，因此主字符串必然包含子字符串中的所有字符。

這些測試用例涵蓋了不同的場景，從基礎情況到邊緣情況，有助于驗證代碼的正確性和健壯性。