题目大意:
给你一个加密的数字字符串,问你一共有多少种不同的解密方式。
Problem:
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
Solution:
C++
Time complexity: O(n^2)
Space complexity: O(n^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Runtime: 6 ms class Solution { public: int numDecodings(string s) { if(s.length() == 0) return 0; m_ways[""] = 1; return ways(s); } private: int ways(const string& s) { if (m_ways.count(s)) return m_ways[s]; if (s[0] == '0') return 0; if (s.length() == 1) return 1; int w = ways(s.substr(1)); const int prefix = stoi(s.substr(0, 2)); if (prefix <= 26) w += ways(s.substr(2)); m_ways[s] = w; return w; } unordered_map<string, int> m_ways; }; |
C++
Time complexity: O(n)
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Runtime: 3 ms class Solution { public: int numDecodings(string s) { if(s.length() == 0) return 0; return ways(s, 0, s.length() - 1); } private: int ways(const string& s, int l, int r) { if (m_ways.count(l)) return m_ways[l]; if (s[l] == '0') return 0; if (l >= r) return 1; // Single digit or empty. int w = ways(s, l + 1, r); const int prefix = (s[l] - '0') * 10 + (s[l + 1] - '0'); if (prefix <= 26) w += ways(s, l + 2, r); m_ways[l] = w; return w; } // Use l as key. unordered_map<int, int> m_ways; }; |
C++
Time complexity: O(n)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: int numDecodings(string s) { if (s.empty() || s[0] == '0') return 0; if (s.length() == 1) return 1; const int n = s.length(); int w1 = 1; int w2 = 1; for (int i = 1; i < n; ++i) { int w = 0; if (!isValid(s[i]) && !isValid(s[i - 1], s[i])) return 0; if (isValid(s[i])) w = w1; if (isValid(s[i - 1], s[i])) w += w2; w2 = w1; w1 = w; } return w1; } private: bool isValid(const char c) { return c != '0'; } bool isValid(const char c1, const char c2) { const int num = (c1 - '0')*10 + (c2 - '0'); return num >= 10 && num <= 26; } }; |
Related Problems:
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment