FilesExpand file tree

 main

/

0091-decode-ways.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (31 loc) · 962 Bytes

 main

/

0091-decode-ways.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

38 lines (31 loc) · 962 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

Given a string w/ only digits, return # ways to decode it (letter -> digit)

Ex. s = "12" -> 2 (AB 1 2 or L 12), s = "226" -> 3 (2 26 or 22 6 or 2 2 6)

DP: At each digit, check validity of ones & tens, if valid add to # ways

Recurrence relation: dp[i] += dp[i-1] (if valid) + dp[i-2] (if valid)

Time: O(n)

Space: O(n)

*/

class Solution {

public:

int numDecodings(string s) {

if (s[0] == '0') {

return 0;

}

int n = s.size();

vector<int> dp(n + 1);

dp[0] = 1;

dp[1] = 1;

for (int i = 2; i <= n; i++) {

int ones = stoi(s.substr(i - 1, 1));

if (ones >= 1 && ones <= 9) {

dp[i] += dp[i - 1];

}

int tens = stoi(s.substr(i - 2, 2));

if (tens >= 10 && tens <= 26) {

dp[i] += dp[i - 2];

}

}

return dp[n];

}

};