I'm looking to learn more about algorithms by practicing coding problems. I subscribed to the mailinglist of dailycodingproblem.com so I will receive one such problem in my inbox every morning and see if I can solve it before the end of the day. Learn with me!

This problem was asked by Facebook.

Problem:


Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is not allowed.

My thought process:

We can use the indexOf() method to find the presence of certain character codes in the message.

The only way there are actually multiple decoding options is for the numbers 10 through 26. If we encounter a character 1, it can denote either a 1 (the letter a), or be part of a 10, 11, 12 ... 19. If we encounter a character 2, it can denote either a 2, or a 20, 21, ... 26.

So we should check for the presence of the numbers 10 through 26 (i.e. letters J through Z) first.

Intuitively, I would say that the number of possible combinations doubles for every found instance of a number 10 through 26, but that turns out to be false.

After trying some problems, it looks like adding another double meaning follows the Fibonacci sequence, i.e. [1, 1, 2, 3, 5, 8, 13 .. etc]. If you're more of a math person than me, this might have been obvious, but it was quite a breakthrough for me. I'm still not sure why this is the case, but it's pretty clear:

  • Zero double meanings yield 1 possibility e.g. "999"
    --> "iii"
  • One double meanings yield 2 possibilities, e.g "11".
    --> "aa" / "k"
  • Two double meanings yield 3 possibilities, e.g. "111".  
    --> "aaa"/ "ka" / "ak"
  • Three double meanings yield 5 possibilities, e.g. "1111".
    --> "aaaa" / "kaa" / "aka" / "aak" / "kk"

Solution:


let numberOfMeanings = (message) => {
  let indicesJZ = []
  for(let j = 0; j < message.length; j++){ 
    findJ_Z(message, j, indicesJZ)
  }
  let unique = indicesJZ.filter((v, i, a) => a.indexOf(v) === i)
  return fibonacci(unique.length + 1)
}


function findJ_Z(message, index, arr){
  for(let i = 10; i< 27; i++){
    let found = message.indexOf(i, index)
    if(found != -1) arr.push(found)
  }
}

function fibonacci(num){
  if(num <2) return 1
  return fibonacci(num-1) + fibonacci(num-2)
}


First, we brute force search the message string for every possible instance of J-Z (number 10-26) and push the result into an array. Then we filter the array for duplicates. Finally, we return the corresponding Fibonacci number of solutions.

The time complexity of this solution is O(n^2) quadratic time, so not incredibly efficient. Let me know if you have a better solution!