题目描述

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Java 代码

class Solution {
    static Map<Integer,Integer> map;
    public int getTranslationCount(String s) {
        map=new HashMap<>();
     return dfs(s,0);
    }
    static int dfs(String s,int i){
        if(i>=s.length()){
               return 1;
        }
        if(map.get(i)!=null){
            return map.get(i);
        }
        int a=dfs(s,i+1);
        int b=0;
        if(i<s.length()-1){
            int res=(s.charAt(i)-'0')*10+(s.charAt(i+1)-'0');
            if(res>=10&&res<=25){
                b+=dfs(s,i+2);
            }
        }
        map.put(i,a+b);
        return a+b;
    }
}

算法2

(dp) $O(n^2)$

blablabla

时间复杂度

参考文献

Java代码

class Solution {
    public int getTranslationCount(String s) {
        int  n=s.length();
     int f[]=new int[n+5];
     f[0]=1;
     for(int i=1;i<=n;i++){
        //  if(s.charAt(i-1)!='0'){
           f[i]+=f[i-1];
        //  }
         if(i>=2){
             int res=(s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0');
             if(res>=10&&res<26){
                 f[i]+=f[i-2];
             }
         }
     }
     return f[n];
    }
}