diff options
Diffstat (limited to 'decode_ways.cpp')
-rw-r--r-- | decode_ways.cpp | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/decode_ways.cpp b/decode_ways.cpp new file mode 100644 index 0000000..c03bd67 --- /dev/null +++ b/decode_ways.cpp @@ -0,0 +1,23 @@ +#include "leetcode.h" + +class Solution { +public: + int numDecodings(string s) { + int n = s.size(); + vector<int> dp(n + 1, 0); + dp[0] = 1; + for (int i = 0; i < n; ++i) { + if (s[i] != '0') + dp[i + 1] += dp[i]; + if (i >= 1 && + (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))) + dp[i + 1] += dp[i - 1]; + } + return dp[n]; + } +}; + +int main() { + Solution obj; + cout << obj.numDecodings("226"); +} |