FilesExpand file tree

 master

/

DecodeWays.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

38 lines (36 loc) · 1.08 KB

 master

/

DecodeWays.java

Top

File metadata and controls

• Code
• Blame

38 lines (36 loc) · 1.08 KB

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

/*

Author: King, wangjingui@outlook.com

Date: Dec 25, 2014

Problem: Decode Ways

Difficulty: Easy

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

Notes:

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.

Solution: 1. dp. Time : O(n); Space : O(1).

*/

public class Solution {

public int numDecodings(String s) {

if (s.length() == 0 || s.charAt(0) == '0') return 0;

int N = s.length();

int f0 = 1, f1 = 1;

for (int i = 1; i < N; ++i) {

if (s.charAt(i) == '0') f1 = 0;

int num = s.charAt(i) - '0' + (s.charAt(i-1) - '0') * 10;

if (num < 10 || num > 26) {

f0 = 0;

}

int tmp = f1;

f1 = f1 + f0;

f0 = tmp;

}

return f1;

}

}