Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 30, 2022 by Ria Pathak

Concepts Used

Backtracking

Difficulty Level

Easy

Problem Statement :

Given a string containing numeric digits from 2 to 9 inclusive, 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.

Leave a Reply

Your email address will not be published. Required fields are marked *