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 with the help of online coding classes.
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));
      }
    }
  }
Previous post Possible Attack-2
Next post Possible Numbers

Leave a Reply

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