diff options
Diffstat (limited to 'decode_ways.c')
-rw-r--r-- | decode_ways.c | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/decode_ways.c b/decode_ways.c new file mode 100644 index 0000000..705e495 --- /dev/null +++ b/decode_ways.c @@ -0,0 +1,59 @@ +// 91. Decode Ways +#include "leetcode.h" + +/* + * a message containing letters from a - z can be encoded into numbers using the + * following mapping: a -> 1, b -> 2, ..., z -> 26. to decode an encoded + * message, all the digits must be grouped then mapped back into letters using + * the reverse of the mapping above (there may be multiple ways). for example, + * "11106" can be mapped into: "aajf" with the grouping ' 1 1 10 6', "kjf" with + * the grouping '11 10 6'. note that the grouping '(1 11 06)' because '06' + * cannot be mapped into "f" because '6' is different from '06'. given a string + * 's' containing only digits, return the number of ways to decode it. the test + * cases are generated so that the answer fits in a 32-bit integer + */ + +int char_to_int(char *s) { return (s[0] - '0') * 10 + s[1] - '0'; } + +int numDecodings(char *s) { + int n = strlen(s), a = 1, b, tmp = char_to_int(s), c; + if (s[0] == '0') + return 0; + if (!n || n == 1) + return 1; + if (tmp == 10 || tmp == 20) + b = 1; + else if (!(tmp % 10)) + return 0; + else if (tmp > 26) + b = 1; + else + b = 2; + if (n == 2) + return b; + for (int i = 2; i < n; i++) { + tmp = char_to_int(&s[i - 1]); + if (!tmp) + return 0; + else if (tmp && tmp < 10) + c = b; + else if (tmp == 10 || tmp == 20) + c = a; + else if (!(tmp % 10)) + return 0; + else if (tmp > 26) + c = b; + else + c = a + b; + a = b; + b = c; + } + return c; +} + +int main() { + char *s1 = "12", *s2 = "226", *s3 = "06"; + printf("%d\n", numDecodings(s1)); // expepct: 2 + printf("%d\n", numDecodings(s2)); // expepct: 3 + printf("%d\n", numDecodings(s3)); // expepct: 0 +} |