Monday, March 7, 2016

LeetCode OJ - Decode Ways

Problem: 

Please find the problem here.

Solution: 

This problem can be solved with dynamic programming. Consider the last character, suppose it is not '0', then it could be decoded by itself. Maybe the last two characters can be combined and decoded as a single character. So we can write the recurrence relation as follow.

decode_ways[i] = (canDecodeLastDigit ? decode_ways[i - 1] : 0) + (canDecodeLastTwoDigits ? decode_ways[i - 2] : 0)

So here is the code.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/decode-ways/

#include "LEET_DECODE_WAYS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_DECODE_WAYS
{
    class Solution
    {
    public:
        int numDecodings(string s)
        {
            int n = s.length();
            if (n == 0)
            {
                // The judge required that, but technically I think there is exactly 1 way to decode the empty string and the empty message
                return 0;
            }
            int a = 1;                     // decodeWays[i - 2], there is exactly one way to decode the empty string
            int b = (s[0] == '0') ? 0 : 1; // decodeWays[i - 1], there is exactly one way to decode a single digit if it is not zero
            
            for (int i = 2; i <= n; i++)
            {
                char currentCharacter  = s[i - 1];
                char previousCharacter = s[i - 2];
                bool canDoOneDigitDecoding = (currentCharacter != '0');
                bool canDoTwoDigitDecoding = (previousCharacter == '1' || (previousCharacter == '2' && currentCharacter <= '6'));
                int c = (canDoOneDigitDecoding ? b : 0) + (canDoTwoDigitDecoding ? a : 0); // decodeWays[i] = (canDoOneDigitDecoding ? decodeWays[i - 1] : 0) + (canDoTwoDigitDecoding ? decodeWays[i - 2] : 0);
                a = b;
                b = c;
            }
            return b;
        }
    };
};

using namespace _LEET_DECODE_WAYS;

int LEET_DECODE_WAYS()
{
    Solution solution;
    cout << solution.numDecodings("1012") << endl;
    return 0;
}

No comments :

Post a Comment