DEV Community


Posted on

Translating a Number to Alphabet Strings

As I've studied for upcoming job interviews, one question that I came across in a mock interview was the following:

Given an integer, return each string that could be translated from that integer if:

1 -> 'a'
2 -> 'b'
3 -> 'c'
11 -> 'k'
26 -> 'z'

For example, the input 11 should return 'aa' and 'k', because each '1' is translated to 'a', and '11' is translated to 'k'. The input 26 should return 'bf' and 'z', because '2' is translated to 'b', '6' is translated to 'f', and '26' is translated to 'z'.

To tackle this problem, I researched best practices. It seemed that dynamic programming would be well suited for this question. Dynamic programming means 'simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner' (Wikipedia - Dynamic Programming). One solution seemed particularly efficient (by vox, stack overflow) - (small changes made to variable names and comments):

function numTrans(num) {
  //create array of digits
  let numArr = num.toString().split('').map(n => parseInt(n));
  //initialize results array with an array containing the first digit of the input
  let results = [[numArr[0]]];
  //loop through each digit of the input, starting at the 2nd digit
  for (let i = 1; i < numArr.length; i++) {
    //store length of results array before entering inner loop
    let resLen = results.length;
    //loop through each element (translation) in the results array
    for (let y = 0; y < resLen; y++) {
      //calculate the value of the last element of results[y] combined with numArr[i] 
      let newNum = results[y][results[y].length - 1] * 10 + numArr[i];
      //check if newNum is less than or equal to 26, and if it is create a new results element containing all but the last element of results[y] with newNum
      if (newNum <= 26) results.push([...results[y].slice(0, -1), newNum]);
      //push numArr[i] into results[y]
  let alpha = 'abcdefghijklmnopqrstuvwxyz';
  //return results mapped over alpha, then joined, to convert each array of integers into a string
  return => => alpha[n - 1]).join(''));

First s/he coverts the integer that is passed to the function to an array of its digits and saves it as the variable 'numArr'. Next s/he initializes the results array with a single element, an array containing the first digit in 'numArr'.

S/he then constructs an outer loop, which will iterate through each number in 'numArr', starting at the second element, index 1 (because the first element was used to initialize the results array). Inside this loop, s/he declares a variable, resLen, to track the length of the results array before entering the inner loop (without this variable we would append incorrect results to the results array).

The inner loop iterates over each existing result element, i.e. those present before beginning the inner loop. S/he then checks if the the last number in results[y], combined with the current digit s/he's evaluating (numArr[i]) make a number less than or equal to 26. If so, it would justify appending a new element to the results array.

If 'newNum' (the combined number) is less than or equal to 26, s/he pushes a new array into results containing all but the last number of results[y], plus 'newNum'. S/he then pushes the number 'numArr[i]' to the results array being evaluated.

This method ensures that each translation is appending a valid number, without having to solve for each separately.

The last part of the solution is to return the results array, mapped to a string of letters, and joined for each element to culminate in an array of string elements.

While dynamic programming isn't always intuitive, it is very powerful in solving complex problems.

Top comments (0)