Summary : Problems solved with DFS recursions I

interview

---

1. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return [["aa","b"],["a","a","b"]]

Idea:
Given a string with length $n$, for a number $i < n$, if $s.substring(0, i)$ is a palindrome, then keep on searching $s.substring(i,n)$

public boolean isPalindrome(String s){
    int front = 0, back = s.length()-1;
    while(front<back){
        if(s.charAt(front) != s.charAt(back)) return false;
        front++;
        back--;
    }
    return true;
}
public void dfs(List<List<String>> res, String s, ArrayList<String> sol, int cur_idx){
    if(cur_idx == s.length()){
        List<String> path = new ArrayList<String>(sol);
        res.add(path);
        return;
    }
    for(int len=1; len<=s.length()-cur_idx; len++){
        String candidate = s.substring(cur_idx, cur_idx+len);
        if(isPalindrome(candidate)){
            sol.add(candidate);
            dfs(res, s, sol, cur_idx+len);
            sol.remove(sol.size()-1);
        }
    }
}
public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<List<String>>();
    int n = s.length();
    if(n==0) return res;
    ArrayList<String> sol = new ArrayList<String>();
    dfs(res, s, sol, 0);
    return res;
}

2. Restore IP addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Idea:
Similar to the Palindrome Partitioning problem:
Given a string with length $n$, for a number $i < n$, if $s.substring(0, i)$ is a valid number segment, then keep on searching $s.substring(i,n)$

Each number in a valid IP address is in range $[0,255]$.
Note:
1. For the string number representation, make sure check its format: 00111 is not valid
2. Terminate conditions :

- Each valid IP contains only 4 segments
- Terminate if current idx in given string exceeds the range bound

public class Solution {
    public boolean valid(String num){
        if(num.length()>1 && num.charAt(0)=='0') return false; // mistake : 010 is not a valid num
        if(num.length()<=3 && Integer.valueOf(num) < 256) return true;
        return false;
    }
    public void dfs(List<String> res, String s, StringBuilder ip, int cur_idx, int seg_count){
        int n = s.length();
        if(cur_idx==n && seg_count == 4){
            res.add(ip.toString());
            return;
        }
        for (int len=1; len <= 3; len++){
            if(cur_idx+len>n) break; // mistake: must check range bound
            String num = s.substring(cur_idx, cur_idx+len);
            if(valid(num)){
                int pos_backup = ip.length();
                if(ip.length()==0) ip.append(num);
                else ip.append("."+num);
                dfs(res, s, ip, cur_idx+len, seg_count+1);
                ip.delete(pos_backup, ip.length()); // mistake: not staring from cur_idx, since extra dots were added 
            }
        }
    }
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        int n = s.length();
        if(n==0||n>12) return res;
        StringBuilder ip = new StringBuilder();
        dfs(res, s, ip, 0, 0);
        return res;
    }
}

3. 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"].

public void dfs(List<String> res,  String digits, StringBuilder sol, int cur_idx, HashMap<Character, String> letters){
    if(cur_idx == digits.length()) {
        res.add(sol.toString());
        return;
    }
    String candidates = letters.get(digits.charAt(cur_idx));
    for(int i=0; i<candidates.length(); i++){
        sol.append(candidates.charAt(i));
        dfs(res, digits, sol, cur_idx+1,  letters);
        sol.deleteCharAt(sol.length()-1);
    }
}
public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<String>();
    if(digits.length()==0) return res;
    HashMap<Character, String> letters = new HashMap<Character, String>();
    String combs[] = {"","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    for(int i='0'; i<='9'; i++){
        letters.put((char)i, combs[i-'0']); // put(i, ...) will treat i as an integer 
    }
    StringBuilder sol = new StringBuilder();
    dfs(res, digits, sol, 0, letters);
    return res;
}

4. Print Numbers By Recursion

Print numbers from 1 to the largest number with N digits by recursion.

Example
Given N = 1, return [1,2,3,4,5,6,7,8,9].
Given N = 2, return [1,2,3,4,5,6,7,8,9,10,11,12,...,99].

Do it in recursion, with at most N depth.

Idea:
Simulate number using char array : ['0','1','0'] => 10
0-9 Permutations

public void dfs(List<Integer> res, char[] num, int cur_idx, int n){
    if(cur_idx==n-1){
        // convert char array to integer
        int x = 0;
        for(char c : num){
            x = x * 10 + (int) c - (int) '0';
        }
        res.add(x);
        return;
    }
    for(char c='0'; c<='9'; c++){
        num[cur_idx+1] = c;
        dfs(res, num, cur_idx+1, n);
    }
}
public List<Integer> numbersByRecursion(int n) {
    List<Integer> res  = new ArrayList<Integer>();
    if(n==0) return res;
    char num[] = new char[n];
    for(char i='0'; i<='9'; i++){
        num[0]=i;
        dfs(res, num, 0, n);
    }
    res.remove(0); // 0 does not count, always starts from 1
    return res;
}

5. Sudoku Solver (TODO)