Given a string str, consisting of lower case English alphabets and digits(0-9), the task is to print all possible strings in lexicographic order that can be formed by replacing each occurrence of a digit with either ‘x‘, ‘y‘ or ‘z‘.
Example:
Input: str = “a1b2”
Output: axbx axby axbz aybx ayby aybz azbx azby azbz
Explanation: These string are the 9 possible strings printed in lexicographic order which can be formed from “a1b2” by replacing all digits with either ‘x’, ‘y’ or ‘z’.Input: str = “abcdef”
Output: abcdef
Approach: The given problem can be solved using recursion with the help of backtracking. The idea is to create a recursive function, and while iterating the given string, replace each occurrence of a digit with ‘x‘, ‘y‘, and ‘z‘ and recursively call for the remaining string for each of the three strings.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to print all// the possible strings after replacing// the digits, in lexicographic ordervoid allPossibleStrings( string str, string cur, int i){ // If the complete string // has been traversed if (str.size() == cur.size()) { // Print current string cout << cur << " "; return; } // If current character // is a digit if (isdigit(str[i])) { // Recursive call after replacing // current character with x allPossibleStrings( str, cur + "x", i + 1); // Recursive call after replacing // current character with y allPossibleStrings( str, cur + "y", i + 1); // Recursive call after replacing // current character with z allPossibleStrings( str, cur + "z", i + 1); } else { // Recursive call after appending // the current character allPossibleStrings( str, cur + str[i], i + 1); }}// Driver Codeint main(){ string str = "a1b2"; allPossibleStrings(str, "", 0); return 0;} |
Java
// Java program of the above approachclass GFG { // Recursive function to print all // the possible Strings after replacing // the digits, in lexicographic order static void allPossibleStrings( String str, String cur, int i) { // If the complete String // has been traversed if (str.length() == cur.length()) { // Print current String System.out.print(cur + " "); return; } // If current character // is a digit if (Character.isDigit(str.charAt(i))) { // Recursive call after replacing // current character with x allPossibleStrings( str, cur + "x", i + 1); // Recursive call after replacing // current character with y allPossibleStrings( str, cur + "y", i + 1); // Recursive call after replacing // current character with z allPossibleStrings( str, cur + "z", i + 1); } else { // Recursive call after appending // the current character allPossibleStrings( str, cur + str.charAt(i), i + 1); } } // Driver Code public static void main(String args[]) { String str = "a1b2"; allPossibleStrings(str, "", 0); }}// This code is contributed by Saurabh Jaiswal |
Python3
# python3 program of the above approach# Recursive function to print all# the possible strings after replacing# the digits, in lexicographic orderdef allPossibleStrings(str, cur, i): # If the complete string # has been traversed if (len(str) == len(cur)): # Print current string print(cur, end=" ") return # If current character # is a digit if (str[i] >= '0' and str[i] <= '9'): # Recursive call after replacing # current character with x allPossibleStrings(str, cur + "x", i + 1) # Recursive call after replacing # current character with y allPossibleStrings(str, cur + "y", i + 1) # Recursive call after replacing # current character with z allPossibleStrings(str, cur + "z", i + 1) else: # Recursive call after appending # the current character allPossibleStrings(str, cur + str[i], i + 1)# Driver Codeif __name__ == "__main__": str = "a1b2" allPossibleStrings(str, "", 0)# This code is contributed by rakeshsahni |
C#
// C# program of the above approachusing System;class GFG{ // Recursive function to print all// the possible strings after replacing// the digits, in lexicographic orderstatic void allPossibleStrings( string str, string cur, int i){ // If the complete string // has been traversed if (str.Length == cur.Length) { // Print current string Console.Write(cur + " "); return; } // If current character // is a digit if (Char.IsDigit(str[i])) { // Recursive call after replacing // current character with x allPossibleStrings( str, cur + "x", i + 1); // Recursive call after replacing // current character with y allPossibleStrings( str, cur + "y", i + 1); // Recursive call after replacing // current character with z allPossibleStrings( str, cur + "z", i + 1); } else { // Recursive call after appending // the current character allPossibleStrings( str, cur + str[i], i + 1); }}// Driver Codepublic static void Main(){ string str = "a1b2"; allPossibleStrings(str, "", 0);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Recursive function to print all // the possible strings after replacing // the digits, in lexicographic order function allPossibleStrings( str, cur, i) { // If the complete string // has been traversed if (str.length == cur.length) { // Print current string document.write(cur + " "); return; } // If current character // is a digit if (Number.isInteger(parseInt(str[i]))) { // Recursive call after replacing // current character with x allPossibleStrings( str, cur + "x", i + 1); // Recursive call after replacing // current character with y allPossibleStrings( str, cur + "y", i + 1); // Recursive call after replacing // current character with z allPossibleStrings( str, cur + "z", i + 1); } else { // Recursive call after appending // the current character allPossibleStrings( str, cur + str[i], i + 1); } } // Driver Code let str = "a1b2"; allPossibleStrings(str, "", 0); // This code is contributed by Potta Lokesh </script> |
Output
axbx axby axbz aybx ayby aybz azbx azby azbz
Time Complexity: O(3N)
Auxiliary Space: O(N) where n is the recursion stack space.
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!