DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,155 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Decode Ways

Problem statement

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
Enter fullscreen mode Exit fullscreen mode

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)

"KJF" with the grouping (11 10 6)
Enter fullscreen mode Exit fullscreen mode

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the **number* of ways to decode it*.

The answer is guaranteed to fit in a 32-bit integer.

Problem statement taken from: https://leetcode.com/problems/decode-ways

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force solution

A naive approach is to generate all possible combinations and count the number of correct sequences.

This approach is easy to implement but has time complexity of O(2^N).

Dynamic programming

The problem can be solved using dynamic programming approach.

Let's take the string "12". We can decode the string in 2 ways [1, 2] or 12. Now lets append 6 at the end of the string. For the new string the decode ways are 2 + 1 = 3. 2 for the [1, 2, 3] or [12, 3] and 1 for [1, 23].

We solved the subproblem first and used it's solution to solve bigger problem. Thats nothing but dynamic programming approach.

Let's check the algorithm.

- initialize count array: count[n + 1]
- set count[0] = count[1] = 1

- if s[0] == 0 // first character of string is 0
  - return 0

- loop for i = 2; i <= n; i++
  - set count[i] = 0

  // if string is "02" we should not count "02" as a valid case.
  // But if the previous char is greater than 0 we set the current index count same
  // as the previous index count.
  - if s[i - 1] > '0'
    - count[i] = count[i - 1]

  // if string is "32" it is not possible to map to any character.
  // hence we have (i - 2)th index for 1 or 2 and
  // if s[i - 2] is 2 we additionally check for (i - 1)th index to
  // be less than 7.
  - if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7')
    - count[i] += count[i - 2]

- return count[n]
Enter fullscreen mode Exit fullscreen mode

C++ solution

class Solution {
public:
    int countWays(string s, int n){
        int count[n + 1];
        count[0] = 1;
        count[1] = 1;

        if(s[0] == '0')
            return 0;

        for(int i = 2; i <= n; i++){
            count[i] = 0;

            if(s[i - 1] > '0')
                count[i] = count[i - 1];

            if(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7')){
                count[i] += count[i - 2];
            }
        }

        return count[n];
    }

public:
    int numDecodings(string s) {
        return countWays(s, s.size());
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func numDecodings(s string) int {
    count := make([]int, len(s) + 1)
    count[0], count[1] = 1, 1

    if s[0] == '0' {
        return 0
    }

    for i := 2; i <= len(s); i++ {
        if s[i - 1] > '0' {
            count[i] = count[i - 1]
        }

        if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7') {
            count[i] += count[i - 2]
        }
    }

    return count[len(s)]
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var numDecodings = function(s) {
    let count = [];
    count[0] = 1;
    count[1] = 1;

    for(let i = 2; i <= s.length; i++){
        count[i] = 0;

        if(s[i - 1] > '0'){
            count[i] = count[i - 1];
        }

        if(s[i - 2] == '1' || (s[i - 2]) == '2' && s[i - 1] < '7'){
            count[i] += count[i - 2];
        }
    }

    return count[s.length];
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

Input: s = "226"

Step 1: int count[n + 1]
        count[0] = count[1] = 1

Step 2: if s[0] == '0'
        '2' == '0'
        false

Step 3: loop for i = 2; i <= n;
        2 <= 3
        true

        if s[i - 1] > '0'
        s[2 - 1] > '0'
        s[1] > '0'
        '2' > '0'
        true

        count[i] = count[i - 1]
        count[2] = count[2 - 1]
                 = count[1]
                 = 1

        if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))
        s[2 - 2] == '1'
        s[0] == '1'
        '2' == '1'
        false

        s[i - 2] == '2' && s[i - 1] < '7'
        s[2 - 2] == '2' && s[2 - 1] < '7'
        s[0] == '2' && s[1] < '7'
        '2' == '2' && '2' < '7'
        true

        count[2] = count[i] + count[i - 2]
                 = count[2] + count[2 - 2]
                 = 1 + 1
                 = 2

        i++
        i = 3

Step 4: loop for i <= n;
        3 <= 3
        true

        if s[i - 1] > '0'
        s[3 - 1] > '0'
        s[2] > '0'
        '6' > '0'
        true

        count[i] = count[i - 1]
        count[3] = count[3 - 1]
                 = count[2]
                 = 2

        if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))
        s[3 - 2] == '1'
        s[1] == '1'
        '2' == '1'
        false

        s[i - 2] == '2' && s[i - 1] < '7'
        s[3 - 2] == '2' && s[3 - 1] < '7'
        s[1] == '2' && s[2] < '7'
        '2' == '2' && '6' < '7'
        true

        count[3] = count[i] + count[i - 2]
                 = count[3] + count[3 - 2]
                 = 2 + 1
                 = 3

        i++
        i = 4

Step 5: loop for i <= n;
        4 <= 3
        false

Step 6: return count[n]
        count[3] = 3

So the answer we return is 3.
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

"In defense of the modern web" β€” great classic DEV post