0631-0640

631. Design Excel Sum Formula ⋆⋆⋆\star\star\star

632. Smallest Range Covering Elements from K Lists ⋆⋆⋆\star\star\star

633. Sum of Square Numbers ⋆\star

634. Find the Derangement of An Array ⋆⋆\star\star

635. Design Log Storage System ⋆⋆\star\star

636. Exclusive Time of Functions ⋆⋆\star\star

637. Average of Levels in Binary Tree ⋆\star

638. Shopping Offers ⋆⋆\star\star

639. Decode Ways II ⋆⋆⋆\star\star\star

 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
class Solution {
 public:
  int numDecodings(string s) {
    if (s.empty()) return 0;

    long dp1 = count(s[0]);
    long dp2 = 1;

    for (int i = 1; i < s.length(); ++i) {
      long dp = count(s[i]) * dp1 + count(s[i - 1], s[i]) * dp2;
      dp %= int(1e9 + 7);
      dp2 = dp1;
      dp1 = dp;
    }

    return dp1;
  }

 private:
  int count(char c) {
    if (c == '*') return 9;
    return c != '0';
  }

  int count(char c1, char c2) {
    if (c1 == '*' && c2 == '*') return 15;
    if (c1 == '*') return (c2 >= '0' && c2 <= '6') ? 2 : 1;
    if (c2 == '*') {
      if (c1 == '1') return 9;
      if (c1 == '2') return 6;
      return 0;
    }
    return c1 == '1' || (c1 == '2' && c2 <= '6');
  }
};

640. Solve the Equation ⋆⋆\star\star