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

难度: 🌗

问题描述

---

解法

class Solution {
    public int translateNum(int num) {
        // 思路：
        // dp
        String str = String.valueOf(num);
        int len = str.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= len; i ++) {
            int m = i - 1;
            dp[i] = dp[i - 1]; // 单个字符肯定满足条件
            // 判断 m & m - 1 能否满足合法的 两位数
            if(isValid(str, m - 1, m)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[len];
    }

    private boolean isValid(String str, int left, int right) {
        char a = str.charAt(left);
        if(a == '0' || a > '2') {
            return false;
        }
        String cur = str.substring(left, right + 1);
        int val = Integer.valueOf(cur);
        return val >= 10 && val <= 25;
    }
}

---

输出