Last Updated on March 30, 2022 by Ria Pathak
Concepts Used
Backtracking
Difficulty Level
Easy
Problem Statement :
Given a string containing numeric digits from
2to9inclusive, return all possible letter combinations that the number could represent in lexicographical order.
See original problem statement here
Solution Approach :
Introduction :
Idea is to traverse the string and add each character which maps to the string numeric value recursively, removing characters after we have stored it to look for next combination.
Description :
We need to explore all the possible combinations which can be solved with backtracking.
Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem, moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.We will map the numeric values of the phone digits (
2-9) to the strings which it contains (see example). Now we will add each character which maps to the given numeric value and print the string when the length of our generated string reaches the length of the given string (why?). After printing the string we will remove the previous values (backtrack) and try other combinations which are left.
Complexity Analysis :
Space Complexity of this approach would be
O(n)since we are using an array.
Solutions:
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
char map[10][4] = {
{' ', ' ', ' ', ' '}, //0
{' ', ' ', ' ', ' '}, //1
{'a', 'b', 'c', ' '}, //2
{'d', 'e', 'f', ' '}, //3
{'g', 'h', 'i', ' '}, //4
{'j', 'k', 'l', ' '},
{'m', 'n', 'o', ' '},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v', ' '}, //8
{'w', 'x', 'y', 'z'} //9
};
void letterComb(char* digits, int* returnSize, char *result, int ind, char **ans)
{
int i = 0;
char c;
char *letter = map[digits[0] - '0'];
if (digits[0] == 0) {
char *res = malloc(strlen(result) + 1);
strcpy(res, result);
//ans[(*returnSize)] = res;
printf("%s ",res);
(*returnSize)++;
return;
}
while ((c = letter[i]) != ' ') {
result[ind] = c;
letterComb(digits + 1, returnSize, result, ind + 1, ans);
i++;
if (i == 4)
break;
}
return;
}
void letterCombinations(char* digits, int* returnSize) {
int ind = 0, size = 0;
int len = strlen(digits) + 1;
char result[len];
if (digits == NULL || strlen(digits) == 0)
return NULL;
char **ans = (char **) malloc(sizeof (char *) * 32768);
memset(result, 0, len);
letterComb(digits, &size, result, ind, ans);
*returnSize = size;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char str[8];
scanf("%s",str);
int n = strlen(str);
int *size;
letterCombinations( str, &size);
// for(int i=0;i<*size;i++)
printf("\n");
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
vector<string> ans;
string hashh[10] = {"", "","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
void fun(string digits, int index, string state)
{
if(index == (int)digits.size()) {
ans.push_back(state);
// cout<<state<<" ";
return;
}
string digit = hashh[digits[index]-'0'];
for(int i=0;i<(int)digit.length();++i)
{
state += digit[i];
fun(digits, index+1, state);
state.pop_back();
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
ans.clear();
string str;
cin>>str;
if(str.empty()) return{};
fun(str, 0, "");
for(int i=0;i<ans.size();i++)
cout<<ans[i]<< " ";
cout<<endl;
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i=i+1)
{
String s=sc.next();
String [] array={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
recursion(array,s,0,"");
System.out.println();
}
}
static void recursion(String array[],String s,int index,String str)
{
if(index==s.length())
{
System.out.print(str+" ");
return;
}
String temp=array[s.charAt(index)-'0'];
for(int i=0;i<temp.length();i=i+1)
{
recursion(array,s,index+1,str+temp.charAt(i));
}
}
}
hashh = ["", "","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" ] ans = [] def fun( digits, index, state): if(index == len(digits)): ans.append(state) return digit = hashh[int(digits[index])] for i in range(len(digit)): state += digit[i] fun(digits, index+1, state) state = state[:-1] for _ in range(int(input())): ans = [] s = input() fun(s, 0, "") for i in ans: print(i, end = " ") print()
[forminator_quiz id="2218"]
This article tried to discuss concept of Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.