Given two strings str1 and str2 each of length N, the task is to generate and print all possible strings of length N such that the character at index i of the generated string is either str1[i] or str2[i]
Examples:
Input: str1 = “abc”, str2 = “def”
Output:
abc
abf
aec
aef
dbc
dbf
dec
def
Input: str1 = “a”, str2 = “b”
Output:
a
b
Approach: The problem can be solved using recursion and at each recursive call, we need to select either the character at str1[i] or the character at str2[i] and append it to the resultant string. The termination condition will be when the length of the resultant string becomes equal to the length of the given strings.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Recursive function to generate// the required stringsvoid generateStr(char* a, char* b, string s, int count, int len){ // If length of the current string is // equal to the length of the given // strings then the current string // is part of the result if (count == len) { cout << s << endl; return; } // Choosing the current character // from the string a generateStr(a + 1, b + 1, s + (*a), count + 1, len); // Choosing the current character // from the string b generateStr(a + 1, b + 1, s + (*b), count + 1, len);}// Driver codeint main(){ char *a = "abc", *b = "def"; int n = strlen(a); // Third argument is an empty // string that we will be appended // in the recursion calls // Fourth arguments is the length of // the resultant string so far generateStr(a, b, "", 0, n); return 0;} |
Java
// Java implementation of the approachclass GFG { // Recursive function to generate // the required strings public static void generateStr(String a, String b, String s, int count, int len) { // If length of the current string is // equal to the length of the given // strings then the current string // is part of the result if (count == len) { System.out.println(s); return; } // Choosing the current character // from the string a generateStr(a.substring(1), b.substring(1), s + a.charAt(0), count + 1, len); // Choosing the current character // from the string b generateStr(a.substring(1), b.substring(1), s + b.charAt(0), count + 1, len); } // Driver code public static void main(String[] args) { String a = "abc", b = "def"; int n = a.length(); // Third argument is an empty // string that we will be appended // in the recursion calls // Fourth arguments is the length of // the resultant string so far generateStr(a, b, "", 0, n); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the approach# Recursive function to generate# the required stringsdef generateStr(a, b, s, count, len): # If length of the current string is # equal to the length of the given # strings then the current string # is part of the result if (count == len): print(s); return; # Choosing the current character # from the string a generateStr(a[1:], b[1:], s + a[0], count + 1, len); # Choosing the current character # from the string b generateStr(a[1:], b[1:], s + b[0], count + 1, len);# Driver codea = "abc"; b = "def";n = len(a);# Third argument is an empty# string that we will be appended# in the recursion calls# Fourth arguments is the length of# the resultant string so fargenerateStr(a, b, "", 0, n);# This code is contributed by Princi Singh |
C#
// C# implementation of the approachusing System; class GFG { // Recursive function to generate // the required strings public static void generateStr(String a, String b, String s, int count, int len) { // If length of the current string is // equal to the length of the given // strings then the current string // is part of the result if (count == len) { Console.WriteLine(s); return; } // Choosing the current character // from the string a generateStr(a.Substring(1), b.Substring(1), s + a[0], count + 1, len); // Choosing the current character // from the string b generateStr(a.Substring(1), b.Substring(1), s + b[0], count + 1, len); } // Driver code public static void Main(String[] args) { String a = "abc", b = "def"; int n = a.Length; // Third argument is an empty // string that we will be appended // in the recursion calls // Fourth arguments is the length of // the resultant string so far generateStr(a, b, "", 0, n); }}// This code is contributed by Rajput-Ji |
Javascript
<script>//javascript implementation of the approach // Recursive function to generate // the required strings function generateStr( a, b, s, count, len ) { // If length of the current string is // equal to the length of the given // strings then the current string // is part of the result if (count == len) { document.write(s + "<br>"); return; } // Choosing the current character // from the string a generateStr(a.substring(1), b.substring(1), s + a[0], count + 1, len); // Choosing the current character // from the string b generateStr(a.substring(1), b.substring(1), s + b[0], count + 1, len); } // Driver code var a = "abc", b = "def"; var n = a.length; // Third argument is an empty // string that we will be appended // in the recursion calls // Fourth arguments is the length of // the resultant string so far generateStr(a, b, "", 0, n); </script> |
Output:
abc abf aec aef dbc dbf dec def
Time Complexity: O(n)
Auxiliary Space: O(n) // due to recursive call stack
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
