题解 | #把数字翻译成字符串#

把数字翻译成字符串

https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668

package main

import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 解码
 * @param nums string字符串 数字串
 * @return int整型
 */
// 题目主要信息:
// 字母到数字分别为 1-26 映射,没有 0
// 输入的数字是字符串,故非常大
// 对于普通数组 1-9,译码方式只有一种,但是对于 11-19,21-26,译码方式有可选择的两种方案
func solve(nums string) int {
	// write code here
	if strings.Compare(nums, "0") == 0 {
		return 0
	}

	if strings.Compare(nums, "10") == 0 || strings.Compare(nums, "20") == 0 {
		return 1
	}

	// 当 0 的前面不是 1 或 2 时,无法译码
	for i := 1; i < len(nums); i++ {
		if nums[i] == '0' {
			if nums[i-1] != '1' && nums[i-1] != '2' {
				return 0
			}
		}
	}

	// 辅助数组 dp 表示前 i 个数的译码方法有多少种
	dp := make([]int, len(nums)+1)
	for i := range dp {
		dp[i] = 1
	}

	for i := 2; i <= len(nums); i++ {
		// 11-19,21-26
		if (nums[i-2] == '1' && nums[i-1] > '0') || (nums[i-2] == '2' && nums[i-1] > '0' && nums[i-1] < '7') {
			dp[i] = dp[i-1] + dp[i-2]

			continue
		}

		dp[i] = dp[i-1]
	}

	return dp[len(nums)]
}

全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务