LeetCode: Decode Ways

一开始dfs runtime exceed, 后来用dp想复杂了就看网上答案

 1 class Solution {
 2 public:
 3     int numDecodings(string s) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int sum = 0;
 7         if (s.size() == 0) return sum;
 8         if (s.size() == 1 && s[0] >= '1' && s[0] <= '9') return 1;
 9         if (s[0] == '0') return 0;
10         vector<int> ret(s.size());
11         ret[0] = 1;
12         for (int i = 1; i < s.size(); i++) {
13             if (s.substr(i-1, 2) >= "10" && s.substr(i-1, 2) <= "26") {
14                 if (i > 1) ret[i] += ret[i-2];
15                 else ret[i] += 1;
16             }
17             if (s[i] >= '1' && s[i] <= '9') ret[i] += ret[i-1];
18         }
19         return ret[s.size()-1];
20     }
21 };

 1 public class Solution {
 2     public int NumDecodings(string s) {
 3         int sum = 0;
 4         if (s.Length == 0) return sum;
 5         if (s.Length == 1 && s[0] >= '1' && s[0] <= '9') return 1;
 6         if (s[0] == '0') return 0;
 7         int[] ans = new int[s.Length];
 8         ans[0] = 1;
 9         for (int i = 1; i < s.Length; i++) {
10             if (string.Compare(s.Substring(i-1, 2), "10") >= 0 && string.Compare(s.Substring(i-1, 2), "26") <= 0) {
11                 if (i > 1) ans[i] += ans[i-2];
12                 else ans[i]++;
13             }
14             if (s[i] >= '1' && s[i] <= '9') ans[i] += ans[i-1];
15         }
16         return ans[s.Length-1];
17     }
18 }

View Code