Strobogrammatic Number III

Description

null

Solution(javascript)

/**
 * @param {string} low
 * @param {string} high
 * @return {number}
 */
const strobogrammaticInRange = function (low, high) {
  const findStrobogrammatic = function (n) {
    const map = {
      6: '9',
      9: '6',
      1: '1',
      0: '0',
      8: '8',
    }
    const result = []
    const candidates = ['9', '6', '1', '0', '8']
    const aux = (remain, left, right) => {
      // 注意 "00" 不对， "00"就是 "0"
      if (left[0] === '0') {
        return
      }

      if (remain === 0) {
        result.push(left + right)
        return
      }
      if (remain === 1) {
        result.push(
          `${left}1${right}`,
          `${left}0${right}`,
          `${left}8${right}`,
        )
        return
      }
      for (let i = 0; i < candidates.length; i++) {
        aux(remain - 2, left + candidates[i], map[candidates[i]] + right)
      }
    }
    aux(n, '', '')
    return result
  }
  let count = 0
  for (let i = low.length; i <= high.length; i++) {
    const result = findStrobogrammatic(i)
    count += result.filter(x => Number(x) >= Number(low) && Number(x) <= Number(high)).length
  }
  return count
}