46. 把数字翻译成字符串

 111->AK,KA,AAA
从左往右尝试的模型
char[],i
从i开始尝试
i=1 ->A
可以当一个,也可以当两个,但要排除0
i=2时可以当一个,也可以当两个,但第二个要<=6
eg:
1 1 1
0 1 2
拿1个位置去转
拿两个位置去转
同时判断拿1个位置或两个位置去转时是否是有效的,这个决定是否是有效的决定
i ->f(i+1)
i,i+1 ->f(i+2)
无效的决定如何考虑?
拿1个位置去转时,0是无效解
拿2个位置去转时,>26是无效解

 public static int number(String str){
        if(str==null||str.length()==0){
            return 0;
        }
        return process(str.toCharArray(),0);
    }


    /**
     *
     i 之前的位置,如何转化已经做过决定了,不用再关心
     str[i.....]有多少种转化的结果
     */
    public static int process(char[] str,int i){

        //base case
       //字符处理完成,可以当成一种结果
        if(i==str.length){
            //转化的过程中,之前做的决定都构成后续,当来到终点位置时,构成一种有效结果
            return 1;
        }
        //说明还有字符,i没有到终止位置
        // 0单独出现,没有这种可能
        if(str[i]=='0'){
            return 0;
        }

        //当i=1时,有两种选择,选1个转,选2个转
        if(str[i]=='1'){
            //选1个转,i来到下一个位置
            int res=process(str,i+1);
            //i+1没有越界的时候,可以选2个字符来转
            if(i+1<str.length){
                res+=process(str,i+2);
            }
            return res;
        }
       //当i=2时,有两种选择,选1个转,选2个转
        if(str[i]=='2'){
            int res=process(str,i+1);
            //选2个转时,要满足以下条件:不越界,而且第二个数的范围在0-6
            if(i+1<str.length && (str[i+1]>='0'&& str[i+1]<='6')){
                res+=process(str,i+2);
            }
            return res;
        }

        //当>2时,只能选一个转
        return process(str,i+1);
    }

  

给定一个数字,我们按照如下规则把它翻译为字符串:

0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。

一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

示例 1:

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

class Solution {
    public int translateNum(int num) {
        String str=String.valueOf(num);
        char[] chs=str.toCharArray();
        return process(chs,0);


    }

    private int process(char[] chs,int i){
        //base case
        if(i==chs.length){
            return 1;
        }

        if(chs[i]=='1'){
            int res=process(chs,i+1);
            if(i+1<chs.length){
                res+=process(chs,i+2);
            }
            return res;
        }

        if(chs[i]=='2'){
            int res=process(chs,i+1);
           // if(i+1<chs.length && '0'<=chs[i+1]<='5'){ 错误的写法
              if(i+1<chs.length && chs[i+1]>='0' && chs[i+1]<='5'){
                res+=process(chs,i+2);
            }
        }
        return process(chs,i+1);

    }
    }

  

上一篇:Leetcode - 46. 全排列


下一篇:46. 全排列(回溯)