首页 > 代码库 > 091. Decode Ways
091. Decode Ways
1 class Solution { 2 public: 3 int numDecodings(string s) { 4 if (s.size() == 0) return 0; 5 else { 6 vector<int> ways(s.size(), 0); 7 if (s[0] >= ‘1‘ && s[0] <= ‘9‘) ways[0] = 1; 8 else ways[0] = 0; 9 if (s[1] >= ‘1‘ && s[1] <= ‘9‘) ways[1] += ways[0]; 10 if (isValid(s.substr(0, 2))) ways[1] += 1; 11 for (int i = 2; i < s.size(); ++ i) { 12 if (s[i] >= ‘1‘ && s[i] <= ‘9‘) ways[i] += ways[i - 1]; 13 if (isValid(s.substr(i - 1, 2))) ways[i] += ways[i - 2]; 14 } 15 return ways[s.size() - 1]; 16 } 17 } 18 private: 19 bool isValid(string str) { 20 int num = (str[0] - ‘0‘) * 10 + str[1] - ‘0‘; 21 if (num >= 10 && num <= 26) return true; 22 else return false; 23 } 24 };
超时的一个算法:
1 int numDecodings(string s) { 2 if (s.size() == 0) return 0; 3 return func(s, 0); 4 } 5 6 int func(string s, int startPos) { 7 if (startPos >= s.size()) return 1; 8 else { 9 if (startPos == s.size() - 1) { 10 if (s[startPos] != ‘0‘) return 1; 11 else return 0; 12 } 13 else { 14 if (s[startPos] == ‘0‘) return 0; 15 else { 16 if (s[startPos] >= ‘1‘ && s[startPos] <= ‘9‘) { 17 if (startPos + 1 < s.size()) { 18 if (s[startPos + 1] == ‘0‘) { 19 if (s[startPos] == ‘1‘ || s[startPos] == ‘2‘) return func(s, startPos + 2); 20 else return 0; 21 } 22 else { 23 if (s[startPos] >= ‘3‘ && s[startPos] <= ‘9‘) return func(s, startPos + 1); 24 else { 25 if (s[startPos] == ‘1‘ || s[startPos + 1] < ‘7‘) return func(s, startPos + 1) + func(s, startPos + 2); 26 else return func(s, startPos + 1); 27 } 28 } 29 } 30 else return 1; 31 } 32 else { 33 return 0; 34 } 35 } 36 } 37 } 38 }
091. Decode Ways
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。