生成由给定的相应符号替换字母而形成的所有可能字符串

WBOY 转载: 2023-08-31 22:33:06 620浏览

生成所有可能的字符串就是将字符串中的某个字符替换为相应的符号，生成所有可能的字符串。我们将得到一个大小为“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'] = '//m.sbmmt.com/m/faq/#';
   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'] = '//m.sbmmt.com/m/faq/#';
   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;
}