Print All Interleavings of Given Two Strings in C++
A sequence of characters known as an interleaving of two strings preserves the relative order of characters from both strings. As an illustration, the interleavings that can result from the strings "abc" and "xy" are "xyabc", "xaybc", "axybc", "xabyc", "axbyc", "abxyc", "xabcy", "axbcy", "abxcy", and "abcxy".
Statement of the Issue and Description:
We need to identify and publish all character interleaved sequences from two strings while maintaining their original order. It means that the order of the characters in the output sequence must remain the same as it does in the input strings, and each character in the output sequence must either come from the first string or the second string.
Concept to Address the Issue:
Recursive thinking can be used to tackle this issue. Each character in the input strings will be iterated over twice, with the possibility of selecting either a character from the first or second string. We recursively investigate every possibility by adding the chosen character to the result and moving to the next point in the result and the related string.
Pseudo Code to print all overleavings of given two strings in C++:
allInterleavings(a, b, result, n, m, index):
if n equals -1 and m equals -1:
print result
else:
if n >= 0:
result[index] = a[n]
allInterleavings(a, b, result, n - 1, m, index - 1)
if m >= 0:
result[index] = b[m]
allInterleavings(a, b, result, n, m - 1, index - 1)
printResult(a, b):
n = length of a
m = length of b
if n equals 0 or m equals 0:
return
result = array of characters of size n + m + 1
result[n + m] = '\0'
allInterleavings(a, b, result, n - 1, m - 1, n + m - 1)
Algorithm to print all overleavings of given two strings in C++:
1. Main recursive function:
• allInterleavings(a, b, result, n, m, index). It requires the two input strings a and b, the result, the result index, and indices n and m for the corresponding strings.
When both n and m are -1, it means that we have taken into account every character from both strings. At that point, the current result is printed.
2. On the other hand, if n is larger than or equal to 0, we select the character at index n from string a and recursively call allInterleavings with the subsequent index and the decremented n.
3. The same is true if m is higher than or equal to 0. In this case, we select the character at index m from string b and recursively call allInterleavings with the subsequent index and the decremented m.
4. The lengths of the input strings a and b are determined by the function printResult(a, b). There is nothing to interleave if either of them is length 0, so we return.
5. The current interleaved sequence is saved as an array of characters. The last element of the array is set to '0' to end the string.
6. To begin creating the interleavings, we call all allInterleavings with the initial indices and lengths.
Program:
#include <iostream>
using namespace std;
void printInterleavings(string str1, string str2, string interleaved = "") {
if (str1.empty() && str2.empty()) {
cout << interleaved << endl;
return;
}
if (!str1.empty()) {
printInterleavings(str1.substr(1), str2, interleaved + str1[0]);
}
if (!str2.empty()) {
printInterleavings(str1, str2.substr(1), interleaved + str2[0]);
}
}
int main() {
string str1, str2;
cout << "Enter the first string: ";
cin >> str1;
cout << "Enter the second string: ";
cin >> str2;
cout << "Interleavings of the given strings:" << endl;
printInterleavings(str1, str2);
return 0;
}
Output:
![Print All Interleavings of Given Two Strings in C++](https://static.tutorialandexample.com/cpp/print-all-interleavings-of-given-two-strings-in-cpp1.png)
Explanation:
1. Base Case:
- The default scenario determines if str1 and str2 are both empty (that is, they have no further characters to interleave).
- Either it prints the current interleaved string and then returns to resume the recursion if or both strings are empty, indicating that one possible interleaving has been produced.
2. Recursive Calls:
- If str1 contains a character, it adds the first character to the interleaved string if it is not empty. Otherwise, it calls printInterleavings recursively with the first character from str1removed.
- It also calls printInterleavings recursively, with the first character from str2 removed if str2 is not empty, adding the first character of str2 to the interleaved string.
- These iterative calls mimic the interleaving of characters. The interleaved string is updated after each step, which involves taking one character from either str1 or str2.
3. Printing:
- The current interleaved string is produced whenever the base case is reached (both strings are empty). It is one way the input strings might be interleaved.
4. Main Purpose:
- The program accepts two input strings from the user, str1, and str2, in the main function.
- After that, it invokes the printInterleavings function to begin interleaving with these input strings.