repl.it
@jonathanbell/

Find the number of possible string decodings

JavaScript

Determine the number of ways that a string could have been encoded given the encoding where where a => 1, b -> 2, and c => 3, and so on...

fork
loading
main.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Facebook coding interview question:
 * 
 * Given a mapping of the English alphabet where a => 1, b -> 2, and c => 3, and so on ... z => 26
 * Take the mapping (example 'ab' => '12') and determine the number of ways that this string ('12')
 * could be interperated. In other words, how many different ways could the original message have 
 * been encoded?
 * 
 * In the example, the result is 2 ('1' = a and '2' = b and '12' = l so 3 possible encodings).
 * 
 * Problem taken from here: https://www.youtube.com/watch?v=qli-JCrSwuk 
 * 
 * Params:
 * 
 * data = string of numbers like '123'
 * k = non-negative integer
 */
const helper = (data, k) => {
  if (k === 0) {
    return 1;
  }

  const s = data.length - k;

  if (data[s] === '0') {
    return 0;
  }

  let result = helper(data, k - 1);

  if (k >= 2 && parseInt(data.substring(0, 2)) <= 26) {
    result += helper(data, k - 2);
  }

  return result;
}

const numWays = (data) => {
  return helper(data, data.length);
}

console.log(numWays('1234')); // There are 5 possible ways to decode '1234' because: 
// 1 = a letter, 2 = a letter, 12 = a letter OR 23 = a letter, 3 = a letter, 4 = a letter

console.log(numWays('4321')); 
Native Browser JavaScript