记录

sicilianee 发表于 2018-6-14 12:46
One thing you missed is the mod, which means it could be pretty big.

DP version. Remember to mod.

/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
  if (!s) {return 0}
  const mod = Math.pow(10, 9) + 7
  const len = s.length
  // dp[i], num decodings for s.slice(0, i + 1)
  const dp = Array(len).fill(0)
  for (let i = 0; i < len; i++) {
    const second = []
    const first = []

    // get second list
    const c = s[i]
    if (c === '*') {
      for (let i = 1; i <= 9; i++) {
        second.push(String(i))
      }
    } else {
      // 0 - 9
      second.push(c)
    }
    // get first list
    if (i > 0) {
      const pc = s[i - 1]
      // 10 - 19
      // 20 - 29
      // so only 1 and 2 is allowed
      if (['1', '2'].includes(pc)) {
        first.push(pc)
      } else if (pc === '*') {
        first.push('1', '2')
      }
    }

    let res = 0
    // use only second itself, anything but 0
    const prevCount = i === 0 ? 1 : dp[i - 1]
    const noZero = second.filter(c => c !== '0')
    res += (noZero.length * prevCount) % mod
    // use both second and first
    if (i > 0) {
      const prevTwo = i === 1 ? 1 : dp[i - 2]
      let count = 0
      for (const fc of first) {
        for (const sc of second) {
          const str = fc + sc
          const numStr = Number.parseInt(str, 10)
          if (numStr <= 26) {
            count++
          }
        }
      }
      res = (res + (count * prevTwo) % mod) % mod
    }
    dp[i] = res
  }
  return dp[len - 1]
};


console.log(numDecodings('*') === 9)
console.log(numDecodings('1*') === 18)

sicilianee 发表于 2018-6-14 13:20
DP version. Remember to mod.

/**

space could be reduced to constant. check writeup.

0613 2. Valid Number



/**
* @param {string} s
* @return {boolean}
*/
var isNumber = function(s) {
  // first, trim
  if (!s) {return false}
  s = s.trim()
  if (!s) {return false}
  const range = /[^0-9e.+-]/
  // no other characters
  if (range.test(s)) {
    return false
  }
  // no more than one dot or e
  let dot = 0
  let exp = 0
  for (let c of s) {
    if (c === '.') {dot++}
    if (c === 'e') {exp++}
  }
  if (exp > 1 || dot > 1) {
    return false
  }

  // if has e, split by e, check both sides not empty
  // first, +-000#.#
  // second, +-000#

  const test = (str, withDot) => {
    if (!str) { return false }
    if (['+', '-'].includes(str[0])) {
      str = str.slice(1)
    }
    // nore more +-
    if (/[+-]/.test(str)) {
      return false
    }
    if (withDot) {
      if (str === '.') {
        return false
      }
    } else {
      if (str.includes('.')) {
        return false
      }
    }
    if (!str) {
      return false
    }
    return true
  }

  if (s.includes('e')) {
    let [one, two] = s.split('e')
    if (!test(one, true) || !test(two, false)) {
      return false
    }
  } else {
    if (!test(s, true)) {
      return false
    }
  }
  return true
};


console.log(isNumber('0') === true)
console.log(isNumber('0.1') === true)
console.log(isNumber('abc') === false)
console.log(isNumber('1 a') === false)
console.log(isNumber('2e10') === true)

// my test cases
console.log(isNumber('000000') === true)
console.log(isNumber('+0') === true)
console.log(isNumber('-0e-0') === true)
console.log(isNumber(' -0e-0   ') === true)
console.log(isNumber(' 000-0e-0   ') === false)
console.log(isNumber(' -0.4e004   ') === true)
console.log(isNumber(' e   ') === false)
console.log(isNumber(' -4.e0   ') === true)
console.log(isNumber(' -4.e   ') === false)
console.log(isNumber(' e5   ') === false)

It's been fun.

really fun after going though the records