Solution to Decode Ways by LeetCode

27 Jun

June 27, 2014January 20, 2020 Sheng 1

Question: https://oj.leetcode.com/problems/decode-ways/

Question Name: Decode Ways

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

class Solution:

# @param s, a string

# @return an integer

def numDecodings(self, s):

# Handle with special cases, string is empty or starting with "0".

if s == "" or s[0] == "0": return 0

numDecodingEndingHere = [0] * (len(s) + 1)

numDecodingEndingHere[0] = 1

index = 0

while index < len(s) - 1:

# We cannot decode one single "0"

if s[index] == "0": return 0

# We can decode current character and move to the next position.

numDecodingEndingHere[index+1] += numDecodingEndingHere[index]

# We can also decode current character and the next one at the smae

# time, and then move to the second next position.

if s[index] == "1" or

(s[index] == "2" and s[index+1] in "0123456"):

numDecodingEndingHere[index+2] += numDecodingEndingHere[index]

if s[index+1] == "0":

# In this case, if the next character is "0", we have to

# skip it, because one single "0" is unable to be decoded.

index += 1

index += 1

if s[-1] != "0":

# The last character could be decoded.

numDecodingEndingHere[-1] += numDecodingEndingHere[-2]

return numDecodingEndingHere[-1]

One Reply to “Solution to Decode Ways by LeetCode”

OK, the world has changed… It’s quite normal to see DP in medium level interview questions…
Sheng: That’s definitely the case of your company!
Sad, I am going to retire…

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

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

static inline int noMoreThan26(char l, char h)

{

if (l > '0' && ((l == '1' && h != '0') || (l == '2' && h > '0' && h < '7')))

return 1;

else

return 0;

}

static int check0(char *s)

{

char last = '';

while (0 != *s)

{

if (*s == '0' && last != '1' && last != '2')

return -1;

else

last = *s++;

}

return 0;

}

int numDecodings(char* s) {

int len = strlen(s);

if (len > 0 && 0 == check0(s))

{

long long *memo = (long long*)malloc(sizeof(long long) * len);

memo[0] = 1;

memo[1] = '0' == memo[1] ? memo[0] : memo[0] + noMoreThan26(s[0], s[1]);

for (int i = 2; i < len; ++i)

{

if ('0' != s[i])

{

if (1 == noMoreThan26(s[i - 1], s[i]))

memo[i] = memo[i - 1] + memo[i - 2];

else

memo[i] = memo[i - 1];

}

else

memo[i] = memo[i - 2];

}

return memo[len - 1];

}

else

return 0;

}

Leave a Reply Cancel reply

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...