剑指 Offer 46. 把数字翻译成字符串

摘要

剑指 Offer 46. 把数字翻译成字符串

一、递归算法解析

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

定义递归函数

• dfs 函数求：「当前指针位置到末尾的数字」的翻译方法数。
• 节点的状态用指针表示，dfs 入口传 0。
• 如果指针 和 指针+1 对应的两位数在[10,25]内，则可以直译，有两种选择：
•        翻译1个数，指针走一步，递归调用，返回出剩余数字的翻译方法数。
•        翻译2个数，指针走两步，递归调用，返回出剩余数字的翻译方法数。
•        二者相加，就是当前数字串的翻译方法数。
• 如果指针 和 指针+1 对应的两位数不在[10, 25]内，则无法直译，只有一个选择：
•        翻译1个数，指针走一步，递归调用 dfs，返回出剩余子串的翻译方法数。

package recursion;/*** @Classname JZ46把数字翻译成字符串* @Description TODO* @Date 2023/3/7 22:08* @Created by xjl*/
public class JZ46把数字翻译成字符串 {public int translateNum(int num) {char[] chars = String.valueOf(num).toCharArray();int index = 0;return next(chars, index);}/*** @description 就是可能等于的一个数或者两个字母组合一个数字* @param: chars* @param: index* @date: 2023/3/7 22:08* @return: int* @author: xjl*/private int next(char[] chars, int index) {if (index > chars.length - 1) {return 1;}int one = next(chars, index + 1);int two = 0;if (index < chars.length - 1 && ((chars[index] - '0') * 10 + (chars[index + 1] - '0') > 9 && (chars[index] - '0') * 10 + (chars[index + 1] - '0') < 26)) {two = next(chars, index + 2);}return one + two;}
}

复杂度分析：

• 时间复杂：O(2^n)。每个节点都要遍历，栈的深度n，n是数字字符个数。
• 空间复杂度: O(n)。栈的深度n ，n是数字字符个数。

博文参考

《leetcode》