[Backtracking][Combinations] Letter Combinations of a Phone Number

1. Example

23
for       for ...
2          3       
a    +    d            "ad"
      +    e            "ae"
      +    f             "af"
b    +    d            "bd"
      +    e            "be"
      +    f             "bf"
c    +    d             "cd"
      +    e             "ce"
      +    f              "cf"


Backtracking

sb.append(str.charAt(i));

letterCombinations(digits, index+1, , res);

sb.deleteCharAt(str.length()-1);

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

2. Implementation
Q1: first digit String1 and Second digit String2
A1: nested for loop one char to one char pair O(k^n), k average letter of a number and n is the lenght of digit

"23"
3*3 = 3^2 = 9

// Recursive
// Time:O(k^n) , Sapce:O(n)
// List {"ad", "ae", "cf"}, size is dynamic and so it is List
public List letterCombination(String digits)
{


    

     String[] letters = {"abc", "def", "ghi", "mno", "pqrs", "tuv", "wxyz"};


 

     List res = new LinkedList<>();
     // validate the input
     if ( digits == null || digits.length() == 0)
         return res;


     

     StringBuilder sb = new StringBuilder();
     letterCombinations(digits, 0, letters, sb, res);



     
}
private void letterCombinations(String digits, int index, String[] letters, StringBuilder sb, List res)
{
  



     if (index == digit.length() )
     {
         res.add(sb.toString());
         return;
     }




     int number = digits.charAt(index) - '0';
     //String str = getLetters(number);
     String str = null;
     if (digit == 0)
         str = " ";
     else 
         str = letters[digit-2];






     for (int i = 0 ; i < str.length(); i++)
     {
         sb.append(str.charAt(i));
         letterCombinations(digits, index+1, , res);
         sb.deleteCharAt(str.length()-1);
     }




}

private String getLetters(int number)
// Iterative
{
      switch(number)
      {
         case 0:// zero is a SPACE
            return " ";
         case 2:
            return "abc";
            //break;
         case 3:
            return "def";
            //break;
         case 4:
            return "ghi";
            //break;
         case 5:
            return "jkl";
            //break;
         case 6:
            return "mno";
            //break;
         case 7:
            return "pqrs";
            //break;
         case 8:
            return "tuv";
            //break;
         case 9:
            return "wxyz";
            //break;
         default:    
            return "";
      }
}

3. Similar Ones
two entity with single unit, how many combinations

Combination