檢查是否可以透過新增或刪除 S1 中的字元來獲得 S2 的排列

---

檢查是否可以透過新增或刪除 S1 中的字元來獲得 S2 的排列，是計算機科學中一個常見的問題。這個問題在資料處理、文字分析和模式識別等各個領域都具有重要意義。

在本教程中，我們將使用 C++ 程式語言來解決這個問題。該方法涉及分析 S1 和 S2 的特徵，以確定 S2 是否可以重新排列形成 S1 的排列。我們將提供此方法的 C++ 程式碼以及解釋，以幫助讀者更好地理解問題和解決方案。

在本教程結束時，您將全面瞭解如何解決檢查是否可以透過新增或刪除 S1 中的字元來獲得 S2 的排列這一挑戰。所以讓我們開始吧！

問題陳述

給定兩個字串 S1 和 S2，任務是檢查是否可以透過新增或刪除 S1 中的字元來使 S1 成為 S2 的排列。如果可行，則列印“可以透過新增或刪除 S1 中的字元來獲得 S2 的排列”，否則列印“無法透過新增或刪除 S1 中的字元來獲得 S2 的排列”。

注意：字串的排列是指其字元的重新排列。

現在，讓我們用例子來理解這個陳述。

示例 1

輸入

"listen"; S2 = "silent"

輸出

A permutation of S2 can be obtained by adding or 
removing characters from S1.

解釋：可以透過刪除字元 't' 並將其在正確位置新增字元 'i' 來將字串 S1 轉換為 S2。因此，S1 可以透過新增或刪除 S1 中的字元而成為 S2 的排列。

示例 2

輸入

S1 = "hello"; S2 = "world";

輸出

A permutation of S2 cannot be obtained by adding 
or removing characters from S1.

解釋：無法透過新增或刪除 S1 中的字元來將字串 S1 轉換為 S2。因此，S1 無法透過新增或刪除字元而成為 S2 的排列。

演算法

1. 定義一個名為 ‘checkPermutation’ 的函式，它接收兩個字串 ‘s1’ 和 ‘s2’ 作為輸入。

2. 在 checkPermutation 函式內部，建立 ‘s1’ 和 ‘s2’ 的副本，並分別將其分配給 ‘sorted_s1’ 和 ‘sorted_s2’ 變數。

3. 使用來自 ‘<algorithm>’ 庫的 ‘std::sort’ 函式對 ‘sorted_s1’ 和 ‘sorted_s2’ 字串進行排序。

4. 使用 ‘==’ 運算子比較排序後的字串，以檢查它們是否相等。

5. 如果排序後的字串相等，則從 ‘checkPermutation’ 函式返回 true，表示可以透過新增或刪除 ‘s1’ 中的字元來獲得 ‘s2’ 的排列。

6. 如果排序後的字串不相等，則從 ‘checkPermutation’ 函式返回 ‘false’，表示無法透過新增或刪除 ‘s1’ 中的字元來獲得 ‘s2’ 的排列。

7. 在 ‘main’ 函式中，使用適當的值定義測試字串 ‘s1’ 和 ‘s2’。

8. 使用 ‘s1’ 和 ‘s2’ 作為引數呼叫 ‘checkPermutation’ 函式。

9. 根據 ‘checkPermutation’ 函式的返回值，顯示一條適當的訊息，指示是否可以透過新增或刪除 ‘s1’ 中的字元來獲得 ‘s2’ 的排列。

該演算法遵循一個簡單的排序字串並比較它們以確定它們是否是彼此的排列的方法。排序使我們能夠輕鬆地識別一個字串中存在的字元是否是另一個字串的子集。現在，讓我們藉助 C++ 的示例來理解它。

示例

使用 C++ 實現上述演算法

下面的 C++ 程式定義了一個名為 ‘checkPermutation’ 的函式，它接收兩個字串 ‘s1’ 和 ‘s2’ 作為輸入。它建立字串的副本並對它們進行排序。然後，它比較排序後的字串以檢查它們是否相等。如果它們相等，則表示可以透過新增或刪除 ‘s1’ 中的字元來獲得 ‘s2’ 的排列。

輸入

S1 = "listen"; S2 = "silent";

預期輸出

Expected Output: A permutation of S2 can be 
obtained by adding or removing characters from S1.

示例

#include <iostream>
#include <string>
#include <algorithm>

bool checkPermutation(const std::string& s1, const std::string& s2) {
   // Create copies of the strings and sort them
   std::string sorted_s1 = s1;
   std::string sorted_s2 = s2;
   std::sort(sorted_s1.begin(), sorted_s1.end());
   std::sort(sorted_s2.begin(), sorted_s2.end());
   // Check if the sorted strings are equal
   return sorted_s1 == sorted_s2;
}

int main() {
   std::string s1 = "listen";
   std::string s2 = "silent";
   if (checkPermutation(s1, s2)) {
      std::cout << "A permutation of S2 can be obtained by adding or removing characters from S1.\n";
   } else {
      std::cout << "A permutation of S2 cannot be obtained by adding or removing characters from S1.\n";
   }
   return 0;
}

輸出

A permutation of S2 can be obtained by adding or removing characters from S1.

結論

在本教程中，我們學習了檢查是否可以透過新增或刪除 S1 中的字元來獲得 S2 的排列的問題。此外，我們還開發了一種基於排序的高效演算法。透過比較字串的排序版本，我們可以確定它們的字元是否匹配，而不管順序或附加字元如何。我們希望本教程能幫助您自信地解決涉及排列和字串操作的問題。