Leet Code Letter Combinations of a Phone Number

References:
problem reference
https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

I had referred below solutions to understand the implementation
Solution references:

https://discuss.leetcode.com/topic/6380/my-recursive-solution-using-java
https://algorithmstuff.wordpress.com/tag/letter-combinations-of-a-phone-number/

The key point is that each of the length of string in result array is of size of input string
i.e., len(ad) == len(23)
       len(ae) == len(23)
       len(af) == len(23) ..... so on
Hence the end condition of  the backtracking function will be
if(len(digit) >= input.length()

Solution 1(in Java):

package LetterPhone;

import java.util.ArrayList;

public class Solution {

  

   //store the digit letter combinations for digits 0-9  

   static String[] combination = {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

   

    public static ArrayList<String> letterCombinations(String a) 

{

  ArrayList<String> res = new ArrayList<String>();

  if(a==null ||a.length()==0)

  {

  return res;

  }

   

  StringBuilder temp = new StringBuilder();

        //backtrack the digit string

          backtracking(a,0,temp,res);    

    return res;    

}

   static void backtracking(String input,int digit,StringBuilder temp,ArrayList<String> res)

   {    

           //get the mapping of the current digit 

           //for input = 23

           i.e; if digit is 0  then letters = abc

           i.e; if digit is 1  then letters = def ... so on

  String letters = combination[input.charAt(digit)- 48];   

  for(int i=0;i<letters.length();i++)

  {

  temp.append(letters.charAt(i));

  //first check if digit(the current length  of string) has exceeded input length

                   

                    if(digit==input.length()-1)

  {

  res.add(temp.toString());

  }

  else

  {

  backtracking(input,digit+1,temp,res);

  }

  temp.setLength(temp.length()-1);

  }

   }

public static void main(String args[])

{

System.out.println(letterCombinations("4"));

}

}

In the below solution the difference is that the end condition of backtracking methods is outside the for loop simple variation of the above method

Solution 2(in Java):

package LetterPhone;

import java.util.ArrayList;

public class Solution1 {

    

   static String[] combination = {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 

   public static ArrayList<String> letterCombinations(String a) 

{

  ArrayList<String> res = new ArrayList<String>();

                   

  if(a==null ||a.length()==0)

  {

  return res;

  }

   

  StringBuilder temp = new StringBuilder();

    backtracking(a,0,temp,res);    

    return res;

}

   static void backtracking(String input,int digit,StringBuilder temp,ArrayList<String> res)
   {  
           //first check if digit(the current length  of string) has exceeded input length
       
  if(digit>=input.length())
  {
  res.add(temp.toString());
  return;
  }
   //get the mapping of the current digit
           //for input = 23
           i.e; if digit is 0  then letters = abc
           i.e; if digit is 1  then letters = def ... so on
  String letters = combination[input.charAt(digit)- 48];
 
           for(int i=0;i<letters.length();i++)
  {      
  temp.append(letters.charAt(i));
  backtracking(input,digit+1,temp,res);
  temp.setLength(temp.length()-1);
  }
   }

public static void main(String args[])

{

System.out.println(letterCombinations("23"));

 

}

}