Commitf651cef

applewjg

committed

DecodeWays

Change-Id: I48bcd05ae17fbc67983c3186c7de3f7045e0204c

1 parent962f5e4 commitf651cefCopy full SHA for f651cef

File tree

+38

-0

lines changed

+38

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,38 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 25, 2014`
	`4`	`+ Problem: Decode Ways`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/decode-ways/`
	`7`	`+ Notes:`
	`8`	`+ A message containing letters from A-Z is being encoded to numbers using the following mapping:`
	`9`	`+ 'A' -> 1`
	`10`	`+ 'B' -> 2`
	`11`	`+ ...`
	`12`	`+ 'Z' -> 26`
	`13`	`+ Given an encoded message containing digits, determine the total number of ways to decode it.`
	`14`	`+ For example,`
	`15`	`+ Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).`
	`16`	`+ The number of ways decoding "12" is 2.`
	`17`	`+`
	`18`	`+ Solution: 1. dp. Time : O(n); Space : O(1).`
	`19`	`+ */`
	`20`	`+`
	`21`	`+publicclassSolution {`
	`22`	`+publicintnumDecodings(Strings) {`
	`23`	`+if (s.length() ==0 \|\|s.charAt(0) =='0')return0;`
	`24`	`+intN =s.length();`
	`25`	`+intf0 =1,f1 =1;`
	`26`	`+for (inti =1;i <N; ++i) {`
	`27`	`+if (s.charAt(i) =='0')f1 =0;`
	`28`	`+intnum =s.charAt(i) -'0' + (s.charAt(i-1) -'0') *10;`
	`29`	`+if (num <10 \|\|num >26) {`
	`30`	`+f0 =0;`
	`31`	`+ }`
	`32`	`+inttmp =f1;`
	`33`	`+f1 =f1 +f0;`
	`34`	`+f0 =tmp;`
	`35`	`+ }`
	`36`	`+returnf1;`
	`37`	`+ }`
	`38`	`+}`

Comments

(0)