leetcode把数字翻译成字符串

深藏阁楼爱情的钟 2023-02-16 09:23 91阅读 0赞

## 题目描述： ##

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法  
示例：  
输入: 12258  
输出: 5  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

## 分析： ##

回溯法：看到这个题，我首先想到的是回溯法，回溯法会将每一种可能尝试一遍。我们将数字转换为字符串后，每一次我们都可以取其中的第一个字符或者前两个字符，判断字符整数对应的字母。并将字符串减去选中的字符

动态规划：这个题目也可以利用动态规划解决。假设f(x)表示以第x个数结尾的前缀对应的方案总数，那么对于第i个位置而言，如果它可以和前一个数字组合，组成的数字在10到25之间，那么f(i)=f(i-1)+f(i-2), 否则f(i)=f(i-1)

## 代码： ##

回溯：

def translateNum(num):
            s = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
            res = []
            l = str(num)
            length = len(l)
    
            def solve(s, tar, temp, curr_res):
                if len(temp) == length:       # 已经匹配到末尾
                    res.append(curr_res[:])
                    return 
    
                for i in range(0, 2):
                    if i == 0:        # 选取一个字符
                        c = tar[0]
                        curr_res += s[int(c)]
                        solve(s, tar[1:], temp+c, curr_res+s[int(c)])
                    else:      # 选取两个字符
                        if len(tar) < 2:
                            continue
                        c = tar[0] + tar[1]
                        if int(c) > 25 or int(c) < 10:     # 判断两个字符组合而成的数字是否在10到25之间
                            continue
                        solve(s, tar[2:], temp+c, curr_res+s[int(c)])
                 
            
            solve(s, l, '', '')
    
            return len(res)

动态规划：

def translateNum(num):
            res = [1]
            s = str(num)
            length = len(s)
            if length == 1:
                return 1
                
            if 9 < int(s[0]+s[1]) < 26:
                res.append(2)
            else:
                res.append(1)
    
            for i in range(2, length):
                c = s[i-1] + s[i]
                if 9 < int(c) < 26:
                    res.append(res[i-1]+res[i-2])
                else:
                    res.append(res[i-1])
    
            return res[-1]