資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查給定字串是否可以由其他兩個字串或它們的排列組成
字串是由字元、數字連續組成的序列。它甚至可能包含特殊字元。一個字串可以由多個子字串組成，也稱為單詞。
字串的排列是另一個由同一組字元組成的字串，可能以不同的順序排列。它基本上可以被認為是字串字母的重新排序。例如，abcd 和 badc 是同一個字串的排列。
示例
示例 1：str：“Permutation”
arr：{“repuio”，“mat”，“mtatn”，“mutate”}
輸出：Yes
輸入字串“Permutation”可以由索引為 0 和 2 的字串對組成，即“repuio”和“mtatn”，它們可以重新排列以形成等效字串。
這個問題可以使用 C++ 中的以下兩種方法解決：
使用排序
使用計數排序
方法 1：使用排序
提供了一個字串輸入陣列。在使用 for 迴圈對字串進行巢狀迭代期間，從輸入陣列中捕獲一對字串。如果輸入字串的排序版本以及生成的字串對的排列計算結果為相同的字串，則進行比較。
語法
sort()
C++ 中的 sort() 方法用於對給定字串進行升序或降序排序。
sort(str.begin() , str.end())
引數
str.begin() - 字串的開頭。
str.end() - 字串的結尾。
演算法
步驟 1 - 接受一個輸入字串和一個字串陣列。
步驟 2 - 使用 C++ 中的 sort() 方法對字串進行初始排序。
步驟 3 - 執行字串的巢狀迴圈迭代，其中一次訪問一對字串，使用指標 i 和 j。每次迴圈 j 從索引 i 開始，一直持續到字串的長度。同時訪問索引 i 和 j 處的兩個字串並連線起來。
步驟 4 - 然後使用 sort() 方法再次對連線的字串進行排序。
步驟 5 - 然後比較連線的字串和輸入排序字串。如果它們等效，則返回 true。否則，如果沒有任何對匹配，則返回 false。
示例
以下 C++ 程式碼片段用於將示例字串和字串陣列作為輸入，並找出是否可以使用陣列中的任何字串對生成示例字串：
//including the required libraries
#include <bits/stdc++.h>
using namespace std;
//check if string can be formed by permutations of two strings
bool permutation( string str,vector<string> arr) {
int size = arr.size();
//sorting the given string
sort(str.begin(), str.end());
//extracting two strings at a time
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
//concatenate the pair of string
string concat = arr[i] + arr[j];
// Sort the resultant string
sort(concat.begin(), concat.end());
//comparing if the order of characters in both strings are same
if (concat.compare(str) == 0) {
//if equal
return true;
}
}
}
//no such combination exists
return false;
}
int main(){
//declaring the input string
string str = "tutorials";
//array of strings
vector<string> arr{ "trils", "outa", "ginc", "abc" };
bool res = permutation(str,arr);
if(res)
cout << "Yes, the string can be formed by permutation of two other strings";
else
cout << "No, the string can't be formed by permutation of two other strings";
return 0;
}
輸出
Yes, the string can be formed by permutation of two other strings
方法 2：使用計數排序
提供了一個字串輸入陣列和一個示例字串。使用計數排序對示例字串進行排序。在使用 for 迴圈對字串進行巢狀迭代期間，從輸入陣列中捕獲一對字串。然後，生成連線的字串，也使用計數排序進行排序。如果字串以及生成的字串對的排列計算結果為相同的字串，則進行比較。
計數排序
可以維護一個大小為 26 個字元的陣列，以儲存字串中每個字元出現的頻率。最終，按升序提取字元以獲得排序後的字串。
演算法
步驟 1 - 接受一個輸入字串和一個字串陣列。
步驟 2 - 使用計數排序演算法對字串進行初始排序。
步驟 3 - 執行字串的巢狀迴圈迭代，其中一次訪問一對字串，使用指標 i 和 j。
步驟 4 - 每次迴圈 j 從索引 i 開始，一直持續到字串的長度。同時訪問索引 i 和 j 處的兩個字串並連線起來。
步驟 5 - 然後使用計數排序機制再次對連線的字串進行排序。
步驟 6 - 然後比較連線的字串和輸入排序字串。如果它們等效，則返回 true。否則，如果沒有任何對匹配，則返回 false。
示例
//including the required libraries
#include <bits/stdc++.h>
using namespace std;
// Function to sort the given string
// using counting sort
void countsort(string& str){
//declaring the numbr of characters
int numchar = 26;
//string length
int len = str.length();
//initialise the count of array
int count[numchar] = { 0 };
//declaring an index param
int idx = 0;
//traversing the string
for (int i = 0; i < len; i++) {
char ch = str[i] ;
count[ch - 'a']++;
}
//increasing order insertion
for (int i = 0; i < numchar; i++) {
int j = 0;
for (j=0; j < count[i];j++) {
str[idx] = i + 'a';
idx++;
}
}
}
//check if string can be formed by permutations of two strings
bool permutation( string str,vector<string> arr){
int size = arr.size();
//sorting the given string
countsort(str);
//extracting two strings at a time
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
//concatenate the pair of string
string concat = arr[i] + arr[j];
// Sort the resultant string
countsort(concat);
//comparing if the order of characters in both strings are same
if (concat.compare(str) == 0) {
//if equal
return true;
}
}
}
//no such combination exists
return false;
}
int main(){
//declaring the input string
string str = "tutorials";
//array of strings
vector<string> arr{ "trils", "outa", "ginc", "abc" };
printf("\nString 2:\n");
for (int i = 0; i <4 ; i++){
cout<<arr[i]<<endl;
}
bool res = permutation(str,arr);
if(res)
cout << "Yes, the string can be formed by permutation of two other strings";
else
cout << "No, the string can't be formed by permutation of two other strings";
return 0;
}
輸出
String 2: trils outa ginc abc Yes, the string can be formed by permutation of two other strings
結論
由於計數排序機制僅考慮有限大小（即 26）的字元陣列的評估，因此第二種方法被認為優於第一種方法。第二種方法將多項式時間方法的時間複雜度降低到接近多項式的近似值。
433 次檢視
