How many different ways can a number be decoded

user_13684079 0
Viewed 494

I am confused and Im not sure what to do. The code below is stuff that I jotted down as I was thinking about the solution.

here is the question with example:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

const numDecodings = (s) => {
  // const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')
  // //write an object with alphabets. The numbers will be keys and the letters will be value

  const alphaObject = {
    1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 
    10: 'j', 11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 
    18: 'r', 19: 's', 20: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z'
  };

  const countObj = {};
  // console.log()

  if (s >= "11") {
    s.split("");
    if (!countObj[alphaObject[s]]) {
      return (countObj[alphaObject[s]] = 1);
    }

    //i return the length because
    //i noticed from the examples that the outputs matched the length.
    //since every digit represents a letter.
    //And every letter is a way to do the problem
  } else if (s <= "10") {
    return 1;
  } else if (s === "0") {
    return 0;
  }
  // else if(s.length >= 4){
  //     //test case 1223
  //     //abbc
  //     //lw
  //     //abw
  //     //lbc
  //     //avc
  //     // return s.length + 2
  //     s.alphaObject

  // }
};
//getting it wrong for testcase 0
console.log(numDecodings("14"));
javascript
3 Answers

This can be done recursive:

  • Look if string length is empty than return 1 because the splitting works.

  • If it's a string starts with a '0' at the first position than this couldn't be any solution because (1-26 is only allowed) => return false.

  • If it has length 1 than this is possible (1-9) => return 1.

  • Look if string without first char is a possible solution by recursion Look if there is a second split-method possible with 2 digits.

  • If the string is a least 2 chars long and and the Integer-value is max 26 this could be a solution, go on recursivly without the first 2 chars..

  • Now look if both try are not false => sum up the both return results.

  • If only the second is not false => return this result.

  • Otherwise return the first result.

function numDecodings(string) {
    if (string.length===0)
        return 1;
    else if (string.charAt(0)==='0')
        return false;
    else if (string.length==1)
        return 1;
        
    let one = numDecodings(string.slice(1));
          
    let test = parseInt(string.substr(0,2));
    if (string.length>=2 && test<=26) {
           let two = numDecodings(string.slice(2));
         if (two!=false && one!=false)
             return one+two;
         else if (two!=false)
             return two;
    }
    return one;
}

console.log(numDecodings ('226')); // 2,2,6 / 22,6 / 2,26 =>3
console.log(numDecodings ('1223')); // 1,2,2,3 / 12,2,3 / 12,23 / 1,22,3 / 1,2,23 => 5
console.log(numDecodings ('1203')); // 1,20,3 => 1

user_53245110

enter image description here

I suggest using a finite automata to model the problem as shown above. The program starts at state 0 and parses the input one character after another. It can move to another state if the character that is shown on an arrow is read. The machine can only finish at the final state which is S0. Now we can count the number of possible paths. An example implementation in JavaScript is here:

function count(input) {
    return decodingState0(input);
}

function decodingState0(input) {
    if (input.length === 0) {
        return 1;
    }
    const firstNumber = parseInt(input[0]);
    const remaining = input.substring(1);
    let numberPossibilities = 0;
    if (firstNumber > 0) {
        numberPossibilities += decodingState0(remaining);
    }
    if (firstNumber === 1) {
        numberPossibilities += decodingState1(remaining);
    } else if (firstNumber === 2) {
        numberPossibilities += decodingState2(remaining)
    }
    return numberPossibilities;
}


function decodingState1(input) {
    if (input.length === 0) {
        return 0;
    }
    return decodingState0(input.substring(1));
}


function decodingState2(input) {
    if (input.length === 0 || parseInt(input[0]) > 7) {
        return 0;
    }
    return decodingState0(input.substring(1));
}
user_83767590

it's a hard requirement that for communication letters/words must either have a deliminator (space, comma etc), or must have a fixed amount of space (1 character per letter, 8 bits per character, etc)

without one of those, you don't have a valid communication.

user_122715690
Related