753. Cracking the Safe #

Problem #

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

While entering a password, the last n digits 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:

n will be in the range [1, 4].
k will be in the range [1, 10].
k^n will be at most 4096.

Problem Summary #

There is a safe that requires a password to open. The password is an n-digit number, and each digit of the password is one of the k-digit sequence 0, 1, …, k-1. You can enter the password however you like, and the safe will automatically remember the last n digits entered. If they match, the safe can be opened. For example, assuming the password is “345”, you can enter “012345” to open it, except that you entered 6 characters. Please return the shortest string that can open the safe.

Hints:

The range of n is [1, 4].
The range of k is [1, 10].
The maximum possible value of k^n is 4096.

Solution Ideas #

Given 2 numbers n and k, n means the password has n digits, and k means each password digit is one of k digits. The safe will remember the last n digits entered. Return the shortest string that can open the safe.
Looking at the data range in the problem, the range is very small, so DFS can be considered. To crack the safe, of course we brute-force it and enumerate all possibilities. The problem asks us to output the shortest string; this is the key to this problem. Why is there a shortest one? This involves a greedy idea. If the next recursion can reuse the previous n-1 digits, then the final output string must be the shortest. (I will not prove it here.) For example, in Example 2, the shortest string is 00, 01, 11, 10. Each attempt uses the previous n-1 digits. Once this idea is clear, just use DFS brute-force backtracking.

Code #

const number = "0123456789"

func crackSafe(n int, k int) string {
	if n == 1 {
		return number[:k]
	}
	visit, total := map[string]bool{}, int(math.Pow(float64(k), float64(n)))
	str := make([]byte, 0, total+n-1)
	for i := 1; i != n; i++ {
		str = append(str, '0')
	}
	dfsCrackSafe(total, n, k, &str, &visit)
	return string(str)
}

func dfsCrackSafe(depth, n, k int, str *[]byte, visit *map[string]bool) bool {
	if depth == 0 {
		return true
	}
	for i := 0; i != k; i++ {
		*str = append(*str, byte('0'+i))
		cur := string((*str)[len(*str)-n:])
		if _, ok := (*visit)[cur]; ok != true {
			(*visit)[cur] = true
			if dfsCrackSafe(depth-1, n, k, str, visit) {
				// Only here there is no need to delete
				return true
			}
			delete(*visit, cur)
		}
		// Delete
		*str = (*str)[0 : len(*str)-1]
	}
	return false
}