Decode Ways Solutions in C++

// Source : https://oj.leetcode.com/problems/decode-ways/
// Author : Hao Chen
// Date   : 2014-07-16



#include <iostream>
#include <string>
#include <string.h>
using namespace std;


//Count[i] = Count[i-1]              if S[i-1] is a valid char (not '0')
//         = Count[i-1]+ Count[i-2]  if S[i-1] and S[i-2] together is still a valid char (10 to 26).

int check(char ch){
    //check 0 or not
    return (!isdigit(ch) || ch=='0') ? 0 : 1;
}

int check(char ch1, char ch2){
    //check it's between 10 and 26
    return (ch1=='1' || (ch1=='2' && ch2<='6')) ? 1: 0;
}

int numDecodings(string s) {
    if (s.size()<=0) return 0;
    if (s.size()==1) return check(s[0]);
   
    int* dp = new int[s.size()];
    memset(dp, 0, s.size()*sizeof(int));

    dp[0] = check(s[0]);
    dp[1] = check(s[0]) *  check(s[1]) + check(s[0], s[1]) ;
    for (int i=2; i<s.size(); i++) {
        if (!isdigit(s[i])) break; 
        if (check(s[i])) {
            dp[i] = dp[i-1];
        }
        if (check(s[i-1], s[i])) {
            dp[i] += dp[i-2];
        }
    
    }
    int result = dp[s.size()-1];
    delete[] dp;
    return result;
}


int main(int argc, char**argv)
{
    string s = "123";
    if (argc>1){
        s = argv[1];
    }
    cout << "\"" << s << "\" : " << numDecodings(s) << endl; 
    return 0;
}

#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode pre_head(0);
        pre_head.next = head;
        for (ListNode *p = head; p; )
            if (p->next && p->val > p->next->val) {
                ListNode *i = &pre_head;
                while (!(i->next->val > p->next->val))
                    i = i->next;
                ListNode *pNode = p->next;
                p->next = pNode->next;
                pNode->next = i->next;
                i->next = pNode;
            } else { p = p->next; }
        return pre_head.next;
    }
};

/// Source : https://leetcode.com/problems/decode-ways/
/// Author : liuyubobobo
/// Time   : 2019-09-03

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

private:
    int n;
    vector<int> dp;

public:
    int numDecodings(string s) {

        n = s.size();
        dp.resize(n, -1);
        return dfs(s, 0);
    }

private:
    int dfs(const string& s, int start){

        if(start >= s.size()) return 1;
        if(s[start] == '0') return 0;
        if(dp[start] != -1) return dp[start];

        int res = dfs(s, start + 1);
        if(start + 1 < n && s.substr(start, 2) <= "26")
            res += dfs(s, start + 2);
        return dp[start] = res;
    }
};


int main() {

    cout << Solution().numDecodings("12") << endl;
    cout << Solution().numDecodings("226") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/decode-ways/
/// Author : liuyubobobo
/// Time   : 2019-09-03

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int numDecodings(string s) {

        int n = s.size();
        if(n == 1 || s[0] == '0') return s[0] != '0';

        vector<int> dp(n + 1, 0);
        dp[n] = 1;
        for(int i = n - 1; i >= 0; i --)
            if(s[i] != '0'){
                dp[i] = dp[i + 1];
                if(i + 1 < n && s.substr(i, 2) <= "26") dp[i] += dp[i + 2];
            }

        return dp[0];
    }
};


int main() {

    cout << Solution().numDecodings("12") << endl;  // 2
    cout << Solution().numDecodings("226") << endl; // 3
    cout << Solution().numDecodings("101") << endl; // 1
    cout << Solution().numDecodings("301") << endl; // 0

    return 0;
}