A generalized DP solution using hash table for your reference


  • 0
    H
    // Create a dictionary for decode
    // In this problem, the dictionary is to match 'A' -> 1 ... 'Z'->26
    unordered_set<string> code;
    for (int i=1; i<=26; i++){
        string num = std::to_string(i);
        code.insert(num);
    }
        
    // DP considering size of string >= 2
    vector<int> dp(N);
    dp[0] = 1;
    dp[1] = code.count(s.substr(0,1));
    for (int i=2; i<=N; i++){
        // update possible decode ways for substring s(0,i)
        dp[i] = dp[i-1]*code.count(s.substr(i-1,1)) + dp[i-2] * code.count(s.substr(i-2,2));
    }
    return dp[N];

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.