算法-回溯法/动态规划-把数字翻译成字符串

刺骨的言语ヽ痛彻心扉 2023-02-16 06:55 50阅读 0赞

# 算法-回溯法/动态规划-把数字翻译成字符串 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

## 1.2 题目描述 ##

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258  
输出: 5  
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

# 2 回溯法 #

## 2.1 思路 ##

回溯法，每次要么选一位，要么在符合规则（即两位数字大于9且小于26，可组合为一个代表字符的数字）的时候选两位。

## 2.2 代码 ##

*  常规思路

class Solution { 
        private int result = 0;
        public int translateNum(int num) { 
            char[] numChars = String.valueOf(num).toCharArray();
    
            backtrack(numChars, 0);
    
            return result;
        }
    
        private void backtrack(char[] num, int start){ 
            if(start >= num.length - 1){ 
                // 结束条件
                result++;
                return;
            }
            // 选择第一个
            backtrack(num, start + 1);
            // 如果第一个数和第二个数组成的数字大于9且小于26就可以组成一个字母
            // 否则比如09 26 28 这样的组合是不行的
            int tmp = (num[start] - '0') * 10 + num[start + 1] - '0';
            if(tmp > 9 && tmp < 26){ 
                // 选择前两个
                backtrack(num, start + 2);
            }
        }
    }

*  不用拆分为字符

class Solution { 
        private int result = 0;
        public int translateNum(int num) { 
            backtrack(num);
            return result;
        }
    
        private void backtrack(int num){ 
            if(num == 0){ 
                // 结束条件
                result++;
                return;
            }
            // 选择最后一个
            backtrack(num / 10);
            int two = num % 100;
            if(two > 9 && two < 26){ 
                 // 选择最后两个
                backtrack(num/ 100);
            }
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][2020060910394566.png]  
O(N)

## 2.4 空间复杂度 ##

O(N)

*  所需空间取决于递归栈的深度，每一层递归函数需要 O(1)，所以空间复杂度为 O(N)。

# 3 动态规划 #

## 3.1 思路 ##

使用动态规划思路，dp\[i\]有两种可能：

*  num\[i-1\]和num\[i\]不组合，此时nums\[i\]放入没有什么影响，所以此时等于dp\[i-1\]
 *  num\[i-1\]和num\[I\]组合，此时nums\[i\]就和nums\[i-1\]绑在一起了，只需要考虑dp\[i-2\]

所以dp\[i\] = dp\[i-2\] + dp\[i-1\];

## 3.2 代码 ##

class Solution { 
        public int translateNum(int num) { 
            int result = 0;
            char[] numc = String.valueOf(num).toCharArray();
            int length = numc.length;
            if(length == 1){ 
                return 1;
            }
            int[] dp = new int[length];
            dp[0] = 1;
            int two = (numc[0] - '0') * 10 + numc[1] - '0';
            if(two > 9 && two < 26){ 
                dp[1] = dp[0] + 1;
            } else{ 
                dp[1] = dp[0];
            }
    
            for(int i = 2; i < length; i++){ 
                two = (numc[i - 1] - '0') * 10 + numc[i] - '0';
                if(two > 9 && two < 26){ 
                    dp[i] = dp[i-2] + dp[i-1];
                } else{ 
                    dp[i] = dp[i-1];
                }
            }
            return dp[length - 1];
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200609112756490.png]

## 3.4 空间复杂度 ##

O(N)

[2020060910394566.png]: https://img-blog.csdnimg.cn/2020060910394566.png
[20200609112756490.png]: https://img-blog.csdnimg.cn/20200609112756490.png