753.破解保险箱.md

753.破解保险箱

/*
 * @lc app=leetcode.cn id=753 lang=typescript
 *
 * [753] 破解保险箱
 */

// @lc code=start
function crackSafe1(n: number, k: number): string {}

// @lc code=end
// crackSafe(3, 3)

解法 1: 回溯

function crackSafe2(n: number, k: number): string {
  const strs: string[] = []
  const dfs = (i = 0, path: number[] = []) => {
    if (i === n) {
      strs.push(path.join(''))
      return
    }
    for (let j = 0; j < k; j++) {
      path[i] = j
      dfs(i + 1, path)
    }
  }
  dfs()
  const h = new Array(n).fill(-1),
    e: number[] = [],
    ne: number[] = []
  const add = (i: number, j: number) => (e.push(j), ne.push(h[i]), (h[i] = ne.length - 1))
  for (let i = 0; i < strs.length; i++) {
    for (let j = i + 1; j < strs.length; j++) {
      if (strs[i].slice(1) === strs[j].slice(0, n - 1)) {
        add(i, j)
      }
      if (strs[j].slice(1) === strs[i].slice(0, n - 1)) {
        add(j, i)
      }
    }
  }
  {
    const vis: number[] = [],
      m = k ** n

    let ans: number[] = []
    const dfs = (u = 0, path: number[] = []) => {
      vis[u] = 1
      path.push(u)
      if (path.length === m) {
        ans = path
        return true
      }
      for (let i = h[u]; ~i; i = ne[i]) {
        const v = e[i]
        if (vis[v]) continue
        if (dfs(v, path)) return true
      }
      vis[u] = 0
      path.pop()
    }
    dfs()
    let res = strs[0]
    for (let i = 1; i < ans.length; i++) {
      res += strs[ans[i]].slice(-1)
    }

    return res
  }
}

解法 2: 优化

function crackSafe(n: number, k: number): string {
  const m = k ** n
  let res = ''
  const dfs = (s = '0'.repeat(n), set = new Set<string>([s])) => {
    if (set.size === m) {
      res = s
      return true
    }
    for (let i = 0; i < k; i++) {
      const str = s.slice(s.length - n + 1) + i
      if (set.has(str)) continue
      set.add(str)
      if (dfs(s + i, set)) return true
      set.delete(str)
    }
  }
  dfs()
  return res
}

Case

test.each([
  { input: { n: 2, k: 3 }, output: '01' },
  { input: { n: 1, k: 2 }, output: '01' },
  { input: { n: 2, k: 2 }, output: '00110' },
])('input: n = $input.n, k = $input.k', ({ input: { n, k }, output }) => {
  expect(crackSafe(n, k)).toEqual(output)
})