aboutsummaryrefslogtreecommitdiff
path: root/decode_ways.c
blob: 705e49530a2bd416860364b784676cd22b5e1fd8 (plain)
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
}