FilesExpand file tree

 master

/

DecodeWays.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

39 lines (36 loc) · 879 Bytes

 master

/

DecodeWays.java

Top

File metadata and controls

• Code
• Blame

39 lines (36 loc) · 879 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

39

/**

* A message containing letters from A-Z is being encoded to numbers using the

* following mapping:

*

* 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits,

* determine the total number of ways to decode it.

*

* For example, Given encoded message "12", it could be decoded as "AB" (1 2) or

* "L" (12).

*

* The number of ways decoding "12" is 2.

*/

public class DecodeWays {

public int numDecodings(String s) {

if (s.length() == 0)

return 0;

int[] c = new int[s.length() + 1];

c[0] = 1;

if (s.charAt(0) != '0')

c[1] = c[0];

else

c[1] = 0;

for (int i = 2; i <= s.length(); i++) {

if (s.charAt(i - 1) == '0') {

c[i] = 0;

} else {

c[i] = c[i - 1];

}

if (s.charAt(i - 2) == '1'

|| (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')) {

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

}

}

return c[s.length()];

}

}