Simple Iterative Ruby solution w/ explanation (accepted)


  • 0
    E

    I broke up the problem into 2 functions. This is merely an application of the Cartesian Product generalized to n sets where n >= 2. Here is a great resource http://ndp.jct.ac.il/tutorials/discrete/node28.html

    Using cartesian product for the input of "23" we get ["a", "b", "c"] x ["d", "e", "f"] = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

    Say we want "234" then we would have the following

    ["a", "b", "c"] x ( ["d", "e", "f"] x ["g", "h", "i"] ).

    Therefore we only need to write a function that returns the cartesian product of two arrays. We then can generalize to n > 2 arrays by using the reduce function. The code follows

    def letter_combinations(digits)
      dict = {
        "1" => [],
        "2" => %w(a b c),
        "3" => %w(d e f),
        "4" => %w(g h i),
        "5" => %w(j k l),
        "6" => %w(m n o),
        "7" => %w(p q r s),
        "8" => %w(t u v),
        "9" => %w(w x y z)
      }  
      digits.split("").reverse.map do |digit| 
        dict[digit]
      end.reduce([]) do |result, arr|
        cartesian_product(arr, result)  
      end
    end
    
    def cartesian_product(arrA, arrB)
      return arrB if arrA.length == 0 
      return arrA if arrB.length == 0
      result = []
      for i in (0..arrA.length - 1)
        for j in (0..arrB.length - 1)
          result += [arrA[i] + arrB[j]]
        end 
      end
      result
    end
    

Log in to reply
 

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