1
\$\begingroup\$

Time complexity: I walk the initial unzipped array of keys representing the number O(N) backwards. I then do an inner walk of the proceeding array of letters *O(L^2), mapping it to every value in the target O(T)). finally, I flattening the values and repeat to get O(N^3)

I know this can not be solved in linear time, but can the runtime be improved (maybe recursively) and is my time analysis correct?

let letters_keys = {
  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']
}

function all_possable(num) {
  return num.toString().split('').map(x => new Set(letters_keys[x]))
}

function remp(possable) {
  possable = all_possable(possable)
  possable = possable.map(x => [...x])

  let v = possable.reduceRight((x, a) => {

    if (x.length === 0) {
      x = a
    } else {

     let k = x.map(c => a.map(b => b + c))
      x = k.reduce((acc, a) => acc.concat(a), [])
    }
    return x
  }, [])
  return v.sort()

}

console.log(remp(5678).sort())

\$\endgroup\$
1
\$\begingroup\$

What is your purpose in writing this code?

If the entire task is enumerate the combinations, it's not possible to do less work than going through all combinations. An \$ n \$ digit number will have between \$ 3^n \$ and \$ 4^n \$ possible combinations, depending on how many of those digits are 7s and 9s.

On the other hand, additional knowledge about the purpose of the function could guide the search for something more useful. For example, I imagine this function might then be the input to a filter which narrows them down it to dictionary words. In that case, you could preemptively stop searching if there are no words in the dictionary that start with a given prefix. (The trie data structure is a classic option for keeping track of this sort of thing.)


Assorted other comments on the code

  • Because what you are passing is fundamentally a sequence of keypresses rather than a number per se, consider having remp take a string instead of a number.

  • Set is probably unnecessary expense and complexity if all you want is to enumerate a few characters. Whatever data type you use, consider sharing an object for all usages of a given digit's letters.

  • all_possable isn't a particularly descriptive name for that function. I also have no idea what remp means.

  • Although it doesn't affect the code, the correct spelling is possible.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.