package com.freetymekiyan.algorithms.level.medium;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Given a digit string, return all possible letter combinations that the number could represent.
 * <p>
 * A mapping of digit to letters (just like on the telephone buttons) is given below.
 * <p>
 * http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png
 * <p>
 * Input:Digit string "23"
 * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * <p>
 * Note:
 * Although the above answer is in lexicographical order, your answer could be in any order you want.
 * <p>
 * Company Tags: Amazon, Dropbox, Google, Uber, Facebook
 * Tags: Backtracking, String
 * Similar Problems: (M) Generate Parentheses, (M) Combination Sum, (E) Binary Watch
 */
public class LetterCombinationsOfPhoneNum {

    private static final String[] LETTERS = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };
    private LetterCombinationsOfPhoneNum l;

    /**
     * Backtracking. DFS.
     * Create a result collection and pass it into a backtracking helper.
     * The helper is like a DFS function that generates all possible combinations by:
     * 1) Assign one letter at current level
     * 2) Call the helper recursively to generate the rest
     * Stop when we reach the end of the digits string, and add the combination to result.
     */
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        helper(digits, 0, "", res);
        return res;
    }

    private void helper(String digits, int s, String comb, List<String> res) {
        if (s == digits.length()) { // all digits done, stop
            res.add(comb);
            return;
        }
        String c = LETTERS[digits.charAt(s) - '0']; // note how to get int index
        for (int i = 0; i < c.length(); i++) { // note its i starts from 0
            helper(digits, s + 1, comb + c.charAt(i), res); // backtracking
        }
    }

    /**
     * BFS.
     * Build combination level by level.
     * The length of the combination is the same as the level.
     * Add all possible letters to each of the result in previous level.
     */
    public List<String> letterCombinationsBFS(String digits) {
        LinkedList<String> queue = new LinkedList<>();
        if (digits == null || digits.length() == 0) {
            return queue;
        }
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            char[] letters = LETTERS[digits.charAt(i) - '0'].toCharArray();
            while (queue.peek().length() == i) { // Get all at this level
                String s = queue.poll();
                for (char l : letters) {
                    queue.offer(s + l);
                }
            }
        }
        return queue;
    }

    @Before
    public void setUp() {
        l = new LetterCombinationsOfPhoneNum();
    }

    @Test
    public void testExamples() {
        l.letterCombinations("22");
    }

    @After
    public void tearDown() {
        l = null;
    }
}

@@ -142,24 +142,54 @@
 .ArrayList;%0A
+import java.util.Collections;%0A
 import java.
@@ -1345,92 +1345,21 @@
   * 
-Create a result collection and pass it into a backtracking helper.%0A     * The helper
+The backtrack
  is 
@@ -1487,22 +1487,25 @@
 all the 
-helper
+backtrack
  recursi
@@ -1681,32 +1681,179 @@
 tring digits) %7B%0A
+        if (digits == null %7C%7C digits.isEmpty()) %7B // When digits is %22%22, should return empty.%0A            return Collections.emptyList();%0A        %7D%0A
         List%3CStr
@@ -1882,39 +1882,47 @@
 st%3C%3E();%0A        
-helper(
+backtrack(res, 
 digits, 0, %22%22, r
@@ -1918,21 +1918,16 @@
 s, 0, %22%22
-, res
 );%0A     
@@ -1956,79 +1956,404 @@
     
-private void helper(String digits, int s, String comb, List%3CString%3E res
+/**%0A     * Backtracking.%0A     * Generate combination position by position.%0A     * Get current position's possible letters.%0A     * Append to the combination so far.%0A     * Pass the subset and generated combination to the next call.%0A     * When all digits are used, add combination to the result collection.%0A     */%0A    private void backtrack(List%3CString%3E res, String digits, int start, String comb
 ) %7B%0A
@@ -2365,16 +2365,20 @@
    if (s
+tart
  == digi
@@ -2395,33 +2395,8 @@
 )) %7B
- // all digits done, stop
 %0A   
@@ -2441,32 +2441,33 @@
 turn;%0A        %7D%0A
+%0A
         String c
@@ -2466,16 +2466,18 @@
 String c
+ur
  = LETTE
@@ -2494,16 +2494,20 @@
 charAt(s
+tart
 ) - '0'%5D
@@ -2511,132 +2511,79 @@
 0'%5D;
- // note how to get int index%0A        for (int i = 0; i %3C c.length(); i++) %7B // note its i starts from 0%0A            helper(
+%0A        for (char c : cur.toCharArray()) %7B%0A            backtrack(res, 
 digi
@@ -2587,16 +2587,20 @@
 igits, s
+tart
  + 1, co
@@ -2609,41 +2609,10 @@
  + c
-.charAt(i), res); // backtracking
+);
 %0A   

update Letter Combinations Of Phone Number