產生由給定的相應符號替換字母而形成的所有可能字串

產生所有可能的字串就是將字串中的某個字元替換為對應的符號，產生所有可能的字串。我們將得到一個大小為“N”的字串“s”和一個大小為“M”的字元對的無序映射“mp”。在這裡，我們可以將字串「s」中的 mp[i][0] 替換為 mp[i][1]，這樣我們的任務就是產生所有可能的字串。

範例範例

Input: s = “xyZ”, mp = {‘x’ : ‘$’, ‘y’ : ‘#’, ‘Z’ : ‘^’}
Output: 
xyZ
xy^
x#Z
z#^
$yZ
$y^
$#Z
$#^

解釋 − 在上面的範例中，總共產生了8個字串。

Input: s = “pQ”, mp = {‘p’ : ‘#’, ‘Q’ : ‘$’}
Output:
pQ
#Q
p$
#$

說明 - 在上面的範例中，總共產生了 4 個字串。

Input: s = “w”, mp = {‘w’ : ‘#’}
Output:
w
#

Explanation − 在上面的範例中，總共產生了2個字串。

方法

在這個方法中，我們將使用蠻力的概念來找到所有可能的組合。

• 首先，我們將建立一個函數，該函數將以字串、當前索引和給定的映射作為參數，並且傳回類型將為void。

• 在這個函數中，我們將定義基本條件，即當前索引等於字串的大小，然後我們將列印該字串並從函數中返回。

• 否則，我們將有兩個選擇，一個是不改變當前索引並移動到下一個，這將始終是一個選項。

• 第二個選擇只有在目前字元有替換時才可能發生。如果替換存在，則我們將呼叫替換。

• 之後我們將從函數傳回，它將自動產生所有所需的結果。

讓我們討論上述方法的程式碼，以便更好地理解。

範例

#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible strings by replacing the characters with paired symbols
void possibleStrings(string str, int idx, unordered_map<char, char> mp){
   if (idx == str.size()) {
      cout << str << endl;
      return;
   }
   // Function call with the idx-th character not replaced
   possibleStrings(str, idx + 1, mp);
   // Replace the idx-th character
   str[idx] = mp[str[idx]];
   // Function call with the idx-th character replaced
   possibleStrings(str, idx + 1, mp);
   return;
}
int main(){
   string str = "xyZ";
   unordered_map<char, char> mp;
   mp['x'] = '$';
   mp['y'] = '#';
   mp['Z'] = '^';
   mp['q'] = '&';
   mp['2'] = '*';
   mp['1'] = '!';
   mp['R'] = '@';
   int idx = 0;
   // Call 'possibleStrings' function to generate all possible strings
   //Here in the 'possible strings' function, we have passed string 'str', index 'idx', and map 'mp'
   possibleStrings(str, idx, mp);
   return 0;
}

輸出

xyZ
xy^
x#Z
x#^
$yZ
$y^
$#Z
$#^

時間與空間複雜度

上述程式碼的時間複雜度為O(N*2^N)，因為我們剛剛在N個元素上進行了回溯，其中N是字串's'的大小。

上述程式碼的空間複雜度為O(N*N)，因為我們將字串作為完整的傳送，同時可能存在N個字串的副本。

回溯演算法

在先前的方法中，我們發送的字串沒有指針，這導致佔用了很多空間。為了減少空間和時間複雜度，我們將使用回溯的概念。

範例

#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible strings by replacing the characters with paired symbols
void possibleStrings(string& str, int idx, unordered_map<char, char> mp){
   if (idx == str.size()) {
      cout << str << endl;
      return;
   }
   // Function call with the idx-th character not replaced
   possibleStrings(str, idx + 1, mp);
   // storing the current element 
   char temp = str[idx];
   // Replace the idx-th character
   str[idx] = mp[str[idx]];
   // Function call with the idx-th character replaced
   possibleStrings(str, idx + 1, mp);
   // backtracking 
   str[idx] = temp;
   return;
}
int main(){
   string str = "xyZ";
   unordered_map<char, char> mp;
   mp['x'] = '$';
   mp['y'] = '#';
   mp['Z'] = '^';
   mp['q'] = '&';
   mp['2'] = '*';
   mp['1'] = '!';
   mp['R'] = '@';
   int idx = 0;
   // Call 'possibleStrings' function to generate all possible strings
   //Here in the 'possible strings' function, we have passed string 'str', index 'idx', and map 'mp'
   possibleStrings(str, idx, mp);
   return 0;
}

輸出

xyZ
xy^
x#Z
x#^
$yZ
$y^
$#Z
$#^

時間與空間複雜度

上述程式碼的時間複雜度為O(N*2^N)，因為我們剛剛在N個元素上進行了回溯，其中N是字串's'的大小。

上述程式碼的空間複雜度為O(N)，因為我們傳送的是字串的位址，只會最多有N個堆疊向下。

結論

在本教程中，我們已經實作了一個程序，用給定的符號替換字母來產生所有可能的字串。在這裡，我們已經看到了回溯法的方法，並且程式碼的時間複雜度是O(N*2^N)，其中N是字串的大小，空間複雜度與時間複雜度相同。為了減少空間複雜度，我們已經實現了回溯過程。

以上是產生由給定的相應符號替換字母而形成的所有可能字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！