leetcode：639. 解码方法 II

题目来源

• leetcode：639. 解码方法 II

题目描述

class Solution {
    
public:
    int numDecodings(string s) {
    

    }
};

题目解析

class Solution {
    
    int process(string str, int i){
    
        if(i == str.size()){
    
            return 1;
        }
        
        if(str[i] == '0'){
    
            return 0;
        }
        
        // str[index]有字符且不是'0'
        if(str[i] != '*'){
    
            // str[index] = 1~9
            int p1 = process(str, i + 1);
            if(i + 1 == str.size()){
    
                return p1;
            }
            
            if(str[i + 1] != '*'){
    
                int num = (str[i] - '0') * 10 + str[i + 1] - '0';
                int p2 = 0;
                if(num < 27){
    
                    p2 = process(str, i + 2);
                }
                return p1 + p2;
            }

            // str[i+1] == '*'
            // i i+1 -> 一起转 1* 2* 3* ...9*
            int p2 = 0;
            if(str[i] < '3'){
    
                p2 = process(str, i + 2) * (str[i] == '1' ? 9 : 6);
            }
            return p1 + p2;
        }

        // str[i] == '*' 1~9
        int p1 = 9 * process(str, i + 1); // i 单转 9种
        if(i + 1 == str.size()){
    
            return p1;
        }
        
        if(str[i + 1] != '*'){
    
            // * 0 10 20
            // * 1 11 21
            // * 2 12 22
            // * 3 13 23
            // * 6 16 26
            // * 7 17
            // * 8 18
            // * 9 19
            int p2 = (str[i + 1] < '7' ? 2 : 1) * process(str, i + 2);
            return p1 + p2;
        }else{
    
            // **
            // 11~19 9
            // 21 ~26 6
            // 15
            int p2 = 15 * process(str, i + 2);
            return p1 + p2;
        }
    }
public:
    int numDecodings(string s) {
    
        return process(s, 0);
    }
};