The Coding Pattern Under LeetCode Recursion Part

Let's go over today about how to write readable recursive code with certain coding pattern. 

Firstly, start with example from leetcode, a command question. 

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

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

The problem is asking to have all combination for give numbers.

Step 1: define the static digital -> Letters

Step 2:  define the recursive method.

Since the leetcode had defined the method already: 

public List<String> letterCombinations(String digits) {

we defined public List<String> letterCombinationsRecursive(List<char[]> letterLists, int[] marks, int deep, List<String> combins)

There will be most time have 4 parameters we defined here

List<char[]> letterLists:  the source data used by code.

int[] marks/boolean[] marks: the mark for each selection.

int deep: how many choice we have done, in this case, how many digital we have mapped to letter.

        The deep here can be replaced with Stack<T> for more generic usage. so we can keep tracking 

        of each step status.

List<String> combins: the final result, for some problem, it is not needed if only need find one match and then return. But for this case, we need list all possible combination. 

Inside the code, the first part will be always check the return condition:

 if(deep == letterLists.size()) {
 StringBuilder sb = new StringBuilder();
 for(int i = 0; i < marks.length; i ++) {
 sb.append(letterLists.get(i)[marks[i]]);
 }
 combins.add(sb.toString());
 return;
 }

the second part: recursive + loop + if 

        for this case, loop each letter for digital on processing, then move to next digital recursively. No if needed here since there is no limitation from problem.

        for(int i = 0; i < letterList.length; i ++) {
            marks[deep] = i;
            letterCombinationsRecursionWithPattern(letterLists, marks, deep + 1, combins);
        }

        and the marks is updated and passed the deep + 1 as next level. 

then we are all set.

Most of recursive programing can following the coding pattern above, in summary.

1. define recursive the method(T srcData, int[] marks, int deep, R result)

2. Inside the method:   write down the return condition

3. main body of recusion

    3.1 loop+recursive + if (for a list of choose options, we don't know the length). 

, or just 

    3.2 recursive 1, recursive 2... recursive n + if (for the known choose options, for example, choose or no choose, or move to 4 direction).  

Here is I post the full implements for this problem.

For other more leetcode solution, refer to 

https://github.com/LeiZheng/leetcode

For each of solution, I write down the test case to play with.