在 C++ 中打印两个字符串的所有交叉组合

2024 年 8 月 28 日 | 3 分钟阅读

在本文中，我们将讨论如何在 C++ 中打印给定两个字符串的所有交错。但在深入实现之前，我们将先了解交错。

什么是交错？

两个字符串的交错是通过以所有可能的方式合并两个字符串的字符，同时保持其相对顺序而形成的。例如，“AB”和“CD”的交错是“ABCD”、“ACBD”、“ACDB”、“CABD”、“CADB”和“CDAB”。

打印给定两个字符串所有可能交错的问题是一个常见的递归和动态规划问题。

问题陈述

给定两个字符串str1和str2，打印这两个字符串的所有可能交错。交错字符串保留单个字符串中字符的顺序。

例如

str1 = "AB"

str2 = "CD"

可能的交错

ABCD

ACBD

ACDB

CABD

CADB

CDAB

1. 朴素递归方法

一个简单的递归解决方案是在每一步从任一字符串中选择一个字符来生成所有交错。

如果str1非空，则递归地为str1[1...]和str2生成交错。将str1[0]添加到结果的前面。
如果str2非空，则递归地为str1和str2[1...]生成交错。将str2[0]添加到结果的前面。

基本情况

如果两个字符串都为空，则打印生成的交错。
如果其中一个字符串为空，则只从非空字符串中选择字符。

它的时间复杂度是指数级的O(2^n)，其中 n 是两个字符串的长度。

示例

让我们举一个例子来打印 C++ 中给定两个字符串的所有交错。

#include <iostream>
using namespace std;

// Recursive Function to print interleavings 
void interleave(string s1, string s2, string res) {

 // Base cases
 if (s1.empty() && s2.empty()) {
 cout << res << endl;
 return; 
 }
 
 if (!s1.empty()) {
 interleave(s1.substr(1), s2, res + s1[0]); 
 }
 
 if (!s2.empty()) {
 interleave(s1, s2.substr(1), res + s2[0]);
 }
}

int main() {

 string str1 = "AB";
 string str2 = "CD";
 
 interleave(str1, str2, "");

 return 0;
}

输出

ABCD
ACBD
ACDB
CABD
CADB
CDAB

这会以字典序递归地生成所有有效的交错。

2. 动态规划方法

我们可以使用自底向上的动态规划方法对其进行优化。

创建一个二维矩阵 dp[m+1][n+1] 来存储交错。
从空字符串到完整字符串，对角线填充矩阵。
填充单元格 dp[i][j]
1. 将 str1[i-1] 附加到 dp[i-1][j] 的交错中
2. 将 str2[j-1] 附加到 dp[i][j-1] 的交错中
最终的交错将存储在 dp[m][n] 中。
它将复杂度降低到O(m*n)，因为我们存储结果而不是重新计算。

示例

实现动态规划方法的 C++ 代码

#include <iostream>
#include <vector>
using namespace std;

//Function to print interleavings using DP
void printInterleavings(string s1, string s2){
 
 int m = s1.length();
 int n = s2.length();
 
 // dp table to store interleavings
 vector<vector<vector<string>>> dp(m+1, vector<vector<string>>(n+1)); 
 
 // Base cases
 for(int i=0; i<=m; i++){
 dp[i][0] = {s1.substr(0, i)}; 
 }
 
 for(int j=0; j<=n; j++){
 dp[0][j] = {s2.substr(0, j)};
 }

 // Build interleavings from smaller to larger strings 
 for(int i=1; i<=m; i++){
 for(int j=1; j<=n; j++){
 
 // Append s1[i-1] to previous interleavings
 for(string s: dp[i-1][j]){
 s.push_back(s1[i-1]);
 dp[i][j].push_back(s);
 }
 
 // Append s2[j-1] to previous interleavings 
 for(string s: dp[i][j-1]){
 s.push_back(s2[j-1]);
 dp[i][j].push_back(s);
 }
 }
 }
 
 // Print all interleavings
 for(string s: dp[m][n]){
 cout << s << "\n";
 }
}

int main() {

 string s1 = "AB";
 string s2 = "CD";

 printInterleavings(s1, s2);

 return 0;
}

输出

ABCD
ACBD
ACDB 
CABD
CADB
CDAB

这种自底向上的 DP 方法避免了重复计算，并提高了递归方法的效率。

下一主题C++ 中用于模式搜索的 Aho-Corasick 算法

在 C++ 中打印两个字符串的所有交叉组合

什么是交错？

问题陈述

1. 朴素递归方法

2. 动态规划方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

在 C++ 中打印两个字符串的所有交叉组合

什么是交错？

问题陈述

1. 朴素递归方法

2. 动态规划方法

相关帖子

C++ 类型转换

C++ Edmonds Karp 算法

C++ std::unary_negate()

C++ STL 中的 list::push_front() 和 list::push_back()

C++ STL 中的 multimap::emplace_hint() 函数

C++ 展平链表

C++ 菱形问题

C++ 打印数字三角形程序

C++ 命名约定

C++ 中计算 LCM 的内置函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器