LeetCode 91 解码方式

1 题目描述

一段包含A-Z的文字使用如下映射关系加密为数字。

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个仅包含数字的字符串,计算其有几种解码方式。

例子1:

输入:"12"
输出:2
释义:可以被解码为"AB" (1 2) 或 "L" (12)

例子2:

输入:"226"
输出:3
释义:可以被解码为"BZ" (2 26),"VF" (22 6),或"BBF"

题目出处:LeetCode

2 解决思路

声明函数decode(string, int),第1个参数传字符串,第2个传当前遍历到的标号,总体采用递归思路,初始标号为0,从头至尾遍历字符串(初始为 decode(s, 0)):

a)若已无字符遍历,则说明该种解码情形满足要求,返回1;

b)若当前字符为'0’,则说明该种解码情形无法进行下去,返回0;

c)若为非'0’字符,则至少可以推进一位,解码总数先置为decode(s, i+1);若还满足推进2位的情形,则解码总数加上decode(s, i+2); 递归完成,即可得到结果。

因某些标号对应的值可能造成重复递归计算,程序使用一个map来记录之前算过的标号来实现加速。

3 Golang实现代码

https://github.com/leileiluoluo/

func decode(s string, i int, table map[int]int) int {
	if len(s) == i {
		return 1
	}
	if '0' == s[i] {
		return 0
	}
	// if calculated before, return value directly
	if v, ok := table[i]; ok {
		return v
	}
	num := decode(s, i+1, table)
	if i < len(s)-1 {
		if '1' == s[i] {
			num += decode(s, i+2, table)
		} else if '2' == s[i] && s[i+1] <= '6' {
			num += decode(s, i+2, table)
		}
	}
	table[i] = num
	return num
}

func numDecodings(s string) int {
	table := make(map[int]int)
	return decode(s, 0, table)
}

评论

正在加载评论......