753. Craking the Safe

There is a box protected by a password. The password is a sequence of ndigits where each digit can be one of the first kdigits 0, 1, ..., k-1.

While entering a password, the last ndigits entered will automatically be matched against the correct password.

For example, assuming the correct password is"345", if you type"012345", the box will open because the correct password matches the suffix of the entered password.

Return any password of minimum length that is guaranteed to open the box at some point of entering it.

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:

1. nwill be in the range[1, 4].

2. kwill be in the range[1, 10].

3. k^nwill be at most 4096.

Thoughts:

1. DFS: A hashset and stringbuilder to edit the string. (Original Post)

   1. start: n repeated "0".

   2. transit: all the nodes that have not visited so far.

   3. output: string in stringBuilder. (Guaranteed there is an answer after containing k^n visited distinct strings.

2. Greedy:

   1. start: n repeated "0".

   2. for loop through current digit j from k-1 to 0, append the last with the current digit, add the current substring and append current digit j to the answer if the current substring is not in visited (Original Post)

Code: DFS T: O(k^n);

 class Solution {
    public String crackSafe(int n, int k) {
        String start = String.join("", Collections.nCopies(n, "0"));
        StringBuilder sb = new StringBuilder(start);

        Set<String> visited = new HashSet<>();
        visited.add(start);

        int target = (int) Math.pow(k,n);

        DFS(sb, visited, target, n, k);

        return sb.toString();
    }

    private boolean DFS(StringBuilder sb, Set<String> visited, int target, int n, int k){
        // base case: all n-length combinations among digits 0 ~ (k -1)
        if(visited.size() == target)
            return true;

        String last = sb.substring(sb.length() - ( n - 1));

        /* DFS expansion*/
        for (char ch = '0'; ch < '0' + k; ch ++){
            String cand = last + ch;
            if(!visited.contains(cand)){
                visited.add(cand);
                sb.append(ch);
                if(DFS(sb, visited, target, n, k))
                    return true;
                visited.remove(cand);
                sb.deleteCharAt(sb.length() - 1);
            }
        }

        return false;
    }
}

Code: Greedy T:O(k^n * k)

class Solution {
public:
    string crackSafe(int n, int k) {
        string ans = string(n, '0');
        unordered_set<string> visited;
        visited.insert(ans);

        for(int i = 0; i < pow(k,n);i++){
            string prev = ans.substr(ans.size()-n+1,n-1);
            for(int j = k - 1; j >= 0; j--){
                string now = prev + to_string(j);
                if(!visited.count(now)){
                    visited.insert(now);
                    ans += to_string(j);
                    break;
                }
            }
        }
        return ans;
    }
};