資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學生成所有可能的字串，方法是用給定的符號替換字母
生成所有可能的字串是指用相應的符號替換字串中的字元並生成所有可能的字串。我們將得到一個大小為'N'的字串's'和一個大小為'M'的字元對無序對映'mp'。在這裡，我們可以用'mp[i][1]'替換字串's'中的'mp[i][0]'，我們的任務是生成所有可能的字串。
示例
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
#
說明 − 在上面的例子中，總共生成了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是字串的大小，空間複雜度與時間複雜度相同。為了降低空間複雜度，我們實現了回溯過程。
219 次瀏覽
