搜索
首页后端开发C++生成由给定的相应符号替换字母而形成的所有可能字符串

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

生成所有可能的字符串就是将字符串中的某个字符替换为相应的符号,生成所有可能的字符串。我们将得到一个大小为“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中文网其他相关文章!

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
C#与C:历史,进化和未来前景C#与C:历史,进化和未来前景Apr 19, 2025 am 12:07 AM

C#和C 的历史与演变各有特色,未来前景也不同。1.C 由BjarneStroustrup在1983年发明,旨在将面向对象编程引入C语言,其演变历程包括多次标准化,如C 11引入auto关键字和lambda表达式,C 20引入概念和协程,未来将专注于性能和系统级编程。2.C#由微软在2000年发布,结合C 和Java的优点,其演变注重简洁性和生产力,如C#2.0引入泛型,C#5.0引入异步编程,未来将专注于开发者的生产力和云计算。

C#vs. C:学习曲线和开发人员的经验C#vs. C:学习曲线和开发人员的经验Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显着差异。 1)C#的学习曲线较平缓,适合快速开发和企业级应用。 2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

C#vs. C:面向对象的编程和功能C#vs. C:面向对象的编程和功能Apr 17, 2025 am 12:02 AM

C#和C 在面向对象编程(OOP)中的实现方式和特性上有显着差异。 1)C#的类定义和语法更为简洁,支持如LINQ等高级特性。 2)C 提供更细粒度的控制,适用于系统编程和高性能需求。两者各有优势,选择应基于具体应用场景。

从XML到C:数据转换和操纵从XML到C:数据转换和操纵Apr 16, 2025 am 12:08 AM

从XML转换到C 并进行数据操作可以通过以下步骤实现:1)使用tinyxml2库解析XML文件,2)将数据映射到C 的数据结构中,3)使用C 标准库如std::vector进行数据操作。通过这些步骤,可以高效地处理和操作从XML转换过来的数据。

C#vs. C:内存管理和垃圾收集C#vs. C:内存管理和垃圾收集Apr 15, 2025 am 12:16 AM

C#使用自动垃圾回收机制,而C 采用手动内存管理。1.C#的垃圾回收器自动管理内存,减少内存泄漏风险,但可能导致性能下降。2.C 提供灵活的内存控制,适合需要精细管理的应用,但需谨慎处理以避免内存泄漏。

超越炒作:评估当今C的相关性超越炒作:评估当今C的相关性Apr 14, 2025 am 12:01 AM

C 在现代编程中仍然具有重要相关性。1)高性能和硬件直接操作能力使其在游戏开发、嵌入式系统和高性能计算等领域占据首选地位。2)丰富的编程范式和现代特性如智能指针和模板编程增强了其灵活性和效率,尽管学习曲线陡峭,但其强大功能使其在今天的编程生态中依然重要。

C社区:资源,支持和发展C社区:资源,支持和发展Apr 13, 2025 am 12:01 AM

C 学习者和开发者可以从StackOverflow、Reddit的r/cpp社区、Coursera和edX的课程、GitHub上的开源项目、专业咨询服务以及CppCon等会议中获得资源和支持。1.StackOverflow提供技术问题的解答;2.Reddit的r/cpp社区分享最新资讯;3.Coursera和edX提供正式的C 课程;4.GitHub上的开源项目如LLVM和Boost提升技能;5.专业咨询服务如JetBrains和Perforce提供技术支持;6.CppCon等会议有助于职业

c#vs. c:每种语言都擅长c#vs. c:每种语言都擅长Apr 12, 2025 am 12:08 AM

C#适合需要高开发效率和跨平台支持的项目,而C 适用于需要高性能和底层控制的应用。1)C#简化开发,提供垃圾回收和丰富类库,适合企业级应用。2)C 允许直接内存操作,适用于游戏开发和高性能计算。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热工具

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能