Cracking the Safe.java

H
1534220198
tags: Math, DFS, Greedy

#### Greedy, Iterative
- For 2 passwords, the shortest situation is both passwords overlap for n-1 chars.
- We can use a window to cut out last (n-1) substring and append with new candidate char from [k-1 ~ 0]
- Track the newly formed string; if new, add the new char to overall result
- Note: this operation will run for k^n times: for all spots of [0 ~ n - 1] each spot tries all k values [k-1 ~ 0]
- Same concept as dfs

#### DFS
- Same concept: use window to cut out tail, and append with new candidate
- do this for k^n = Math.pow(k, n) times

```
/*
There is a box protected by a password. The password is n digits, 
where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, 
the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", 
but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box 
after the entire string is inputted.

Example 1:
Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.
Example 2:
Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.
Note:
n will be in the range [1, 4].
k will be in the range [1, 10].
k^n will be at most 4096.

http://www.cnblogs.com/grandyang/p/8452361.html
*/

/*
For 2 passwords, the shortest situation is both passwords overlap for n-1 chars.
We can use a window to cut out last (n-1) substring and append with new candidate char from [k-1 ~ 0]
Track the newly formed string; if new, add the new char to overall result
Note: this operation will run for k^n times: for all spots of [0 ~ n - 1] each spot tries all k values [k-1 ~ 0]

This is more greedy: will generate one correct solution
*/
class Solution {
    public String crackSafe(int n, int k) {
        //if (n == 1) return "0";
        
        Set<String> set = new HashSet<>();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) sb.append("0");
        set.add(sb.toString());
        
        for (int i = 0; i < Math.pow(k, n); i++) {
            String tail = sb.substring(sb.length() - n + 1); // last n - 1 chars
            for (int j = k - 1; j >= 0; j--) {
                String newStr = tail + j;
                if (!set.contains(newStr)) {
                    set.add(newStr);
                    sb.append(j);
                    break;
                }
            }
        }
        
        return sb.toString();
    }
}


// DFS
class Solution {
    public String crackSafe(int n, int k) {        
        Set<String> visited = new HashSet<>();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) sb.append("0");
        visited.add(sb.toString());
        
        // recursive, dfs
        dfs(n, k, Math.pow(k, n), visited, sb);
        return sb.toString();
    }
    
    private void dfs(int n, int k, double total, Set<String> visited, StringBuffer sb) {
        if (visited.size() == total) return;
        String tail = sb.substring(sb.length() - n + 1);
        for (int j = k - 1; j >= 0; j--) {
            String newStr = tail + j;
            if (visited.contains(newStr)) continue;
            visited.add(newStr);
            sb.append(j);
            dfs(n, k, total, visited, sb);
        }
    }
}
```