Dynamic Programming - String Decoder

1. Problem Description
This is a Facebook interview question for software engineers from careercup. Here is the original thread,
"

You are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123". 

For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).

for string "1234" we have following possible combinations, I might be missing some of them but you get the idea

{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}

- sachin323 May 16, 2016 in United States | Report Duplicate | Flag ".

2. Data Structure and Algorithm
Some contributors mentioned on the thread that this is a dynamic problem. In fact the sub-problem is also reasonably obvious to spot. Given an input of number string, for instance "567123432234543789", assume that at position i of this string. Any single number can always be mapped into letters (a-z), ranges from [1, 26], therefore one sub-problem will be finding the decoding of the rest string from i+1 to the end. The second sub-problem may or may not exist, depending on the value at i and its subsequent value in i+1. If they are ranging from [10, 26], representing [j, z], then the second sub-problem exists - find the decoding of i+2 to the rest of string. If they are ranging out of [10, 26], then does not exist a second sub-problem.
For instance "36......",  at position "3" only has one sub-problem of "6......"; "2415......" at position "2" has two sub problems "425......" and "15......".

A special number in the number string is "0", because "0" does not represent any letter, [a, z]. Any problem starting with "0" does not have any sub-problems and it can be terminated because it has not valid decoding.
For instance any input number string starting with "0......", does not have any valid decoding to represent any letter string.

As usual, cache technique is used in my dynamic-programming solution. It takes the sub-problem, the number string, as the key and take how many ways of decoding as value.

3. C++ Implementation
The return value of function "StringDecoder(" will be either greater than 0 or less than 0. A return value greater than 0 indicates how many ways of decoding. And a negative return value indicates failure to find an decoding.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <string>
#include <unordered_map>

bool ValidStringNumber(const std::string &plainText)
{
    if (plainText.empty()) {
        return false;
    }
    {
        auto itEnd = plainText.end();
        for (auto it = plainText.begin(); it != itEnd; ++it) {
            if (*it > '9' || *it < '0') {
                return false;
            }
        }
    }

    return true;
}

using StringDecoderMap = std::unordered_map<std::string, ptrdiff_t>;

ptrdiff_t StringDecoder_R(const std::string &number,
                          const std::string::const_iterator curIt,
                          StringDecoderMap& cache)
{
    if (curIt == number.end()) {
        return 1;
    }
    if (*curIt == '0') {
        return -1;
    }
    auto itNext = curIt + 1;
    if (itNext == number.end()) {
        return 1;
    }

    const std::string key(curIt, number.end());
    auto itFound = cache.find(key);
    if (itFound != cache.end()) {
        return itFound->second;
    }

    ptrdiff_t decodes = -1;;
    ptrdiff_t tempCount = StringDecoder_R(number, itNext, cache);
    if (tempCount >= 0) {
        decodes = tempCount;
    }

    const std::string twoChars(curIt, curIt + 2);
    if (atoi(twoChars.c_str()) <= 26) {
        tempCount = StringDecoder_R(number, ++itNext, cache);
        if (tempCount >= 0) {
            if (decodes > 0) {
                decodes += tempCount;
            }
            else {
                decodes = tempCount;
            }
        }
    }

    cache.insert(std::make_pair(key, decodes));
    return decodes;
}

ptrdiff_t StringDecoder(const std::string &number)
{
    if (!ValidStringNumber(number)) {
        return -1;
    }

    StringDecoderMap cacheMap;
    return StringDecoder_R(number, number.begin(), cacheMap);
}

// ********************************************************************************
// Testing
// ********************************************************************************
#include <cassert>
void TestDecoder()
{
    assert(StringDecoder("134a457") < 0);
    assert(StringDecoder("100") < 0);
    assert(StringDecoder("12") == 2);
    assert(StringDecoder("123") == 3);
    assert(StringDecoder("0123456789") < 0);
    assert(StringDecoder("10123") == 3);
    assert(StringDecoder("345") == 1);
    assert(StringDecoder("1123") == 5);
    assert(StringDecoder("5123") == 3);

}