Javascript via a 1-dimension dynamic programming


  • 0
    L

    The dimension is the length of the digit string. Keep track of the various letter combinations per digit string length in the 'dp' array.

    For example, if the digit string is '23', the dp array is progressively as:
    when str length is 0 => [""]
    when str length is 1 => ["a","b","c"]
    when str length is 2 => ["ad","bd","cd","ae","be","ce","af","bf","cf"]

    Here's the code:

    var letterCombinations = function(digits) {
      const map = {
        '0': [''],
        '1': [''],
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
      }
    
      if (digits.length === 0) {
        return []
      }
      
      const dp = []
      dp[0] = ['']
      
      for (var i=0; i<digits.length; i++) {
        const cur  = digits[i]
        const curDigits = map[cur]
        dp[i+1] = []
        curDigits.forEach(newLetter => {
          dp[i].forEach(existCombo => {
            dp[i+1].push(existCombo + newLetter)
          })
        })
      } //for
      return dp[digits.length]
    }
    

Log in to reply
 

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