DP Javascript Solution


  • 0
    F

    Use two counters each time. Counter A (cta) counts those ends with letters smaller than 10 ("A" ~ "J"), and counter B (ctb) counts those ends with letters between 10 and 26 ("K" ~ "Z").

    In the iteration, keep track of the last character. If current char is "0", cta should be zero since there will be no decodings which ends with a valid letter, otherwise it will be the sum of last cta and ctb (adding a new letter to each one). For ctb, if the number of s[i - 1] + s[i] is valid (<= 26), then it will equal to last cta since for each item just remove the last char and replace with the new letter (>=26).

    var numDecodings = function(s) {
      if (s.startsWith('0')) return 0;
      if (s.length === 0 || s.length === 1) return s.length;
    
      let lastChar = s[0];
      let cta = 1, ctb = 0;
      for (let i = 1; i < s.length; i++) {
        let char = s[i];
        let a = cta;
        let b = ctb;
        if (char !== '0') {
          cta = a + b;
        } else {
          cta = 0;
        }
        if (parseInt(lastChar + char) <= 26) {
          ctb = a;
        } else {
          ctb = 0;
        }
    
        lastChar = char;
      }
    
      return cta + ctb;
    };
    

Log in to reply
 

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