Backtracking and DP in JS


  • 0
    Y

    Backtracking (TLE):

    function numDecodings(string) {
      if (!string || string.charAt(0) === '0') {
        return 0
      }
      const length = string.length
      let count = 0
      function backtrack(start = 0) {
        if (start === length) {
          count++; return
        }
        const firstDigit = parseInt(string.charAt(start), 10)
        if (0 < firstDigit && firstDigit < 3 && start + 1 < length) {
          const nextDigit = parseInt(string.charAt(start + 1), 10)
          if ((firstDigit === 2 && nextDigit < 7) || firstDigit === 1) {
            backtrack(start + 2)
          }
        }
        if (firstDigit) {
          backtrack(start + 1)
        }
      }
      backtrack()
      return count
    }
    

    DP:

    // https://leetcode.com/problems/decode-ways/
    function numDecodings(string) {
      if (!string || string.charAt(0) === '0') {
        return 0
      }
      const length = string.length
      if (length === 1) {
        return 1
      }
      let numWaysToDecode = 0 // current
      let a = 1 // before current
      let b = 1 // before before current
      for (let i = 1; i < length; i++) {
        const digit = Number.parseInt(string.charAt(i))
        const previousDigit = Number.parseInt(string.charAt(i - 1))
        if (digit) {
          numWaysToDecode = a
          if (previousDigit === 1 || (previousDigit === 2 && digit < 7)) {
            numWaysToDecode += b
          }
        } else {
          numWaysToDecode = 0
          if (0 < previousDigit && previousDigit < 3) {
            numWaysToDecode += b
          }
        }
        [a, b] = [numWaysToDecode, a]
      }
      return numWaysToDecode
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.