Share my c# O(N) solution


  • 0
    T

    Base idea is :
    v1[i] means when previous char as i, how many solution
    v2[i] means when previous char as 10+i or 20+i, how many soution

    
    public class Solution {
        public int NumDecodings(string s) {
            var v2 = new int[]{0,0,0,0,0,0,0,0,0,0};
            var v1 = new int[]{0,1,1,1,1,1,1,1,1,1};
            int mod = 1000000007;
            int len = s.Length;
            if(len == 0)
                return 0;
            
            for(int i = 0;i<len;i++){
                var newv1 = new int[10];
                var newv2 = new int[10];
                int sumTotal = 0;
                foreach(var v in v1){
                    sumTotal +=v;
                    sumTotal %=mod;
                }
                foreach(var v in v2){
                    sumTotal +=v;
                    sumTotal %=mod;
                }
                if(s[i] == '*'){
                    for(int j = 1;j<=9;j++){
                        if(i > 0){
                            newv2[j]+=v1[1];
                            if(j<=6)
                                newv2[j]+=v1[2];
                            newv2[j]%=mod;
                        }
                        newv1[j] = i == 0 ? 1 : sumTotal;
                    }
                }else{
                    if(i > 0){
                        newv2[s[i]-'0']+=v1[1];
                        if(s[i] >='0' && s[i] <= '6')
                            newv2[s[i]-'0']+=v1[2];
                        newv2[s[i]-'0']%=mod;
                    }
                    
                    if(s[i] != '0'){
                        newv1[s[i]-'0'] = i == 0? 1 : sumTotal;
                    }
                }
                v1 = newv1;
                v2 = newv2;
            }
            int result = 0;
            foreach(var v in v1){
                result +=v;
                result %=mod;
            }
            foreach(var v in v2){
                result +=v;
                result %=mod;
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.