C# solution: DP, constant space, modified from 70. Climbing Stairs


  • 0
    B
    public class Solution 
    {
        public int NumDecodings(string s) 
        {
            if (s.Length == 0) return 0;
            if (s.Length == 1) return CanDecoding(s[0]) ? 1 : 0;
            if (s.Length == 2)
            {
                return (CanDecoding(s[0]) && CanDecoding(s[1]) ? 1 : 0) + (CanDecoding(s[0], s[1]) ? 1 : 0);
            }
    
            if (s[0] == '0') return 0;
    
            var prePre = CanDecoding(s[0]) ? 1 : 0;
    
            var pre = (CanDecoding(s[0]) && CanDecoding(s[1]) ? 1 : 0) + (CanDecoding(s[0], s[1]) ? 1 : 0);
    
            for (int i = 2; i < s.Length; i++)
            {
                var cur = 0;
                if (CanDecoding(s[i])) cur += pre;
                if (CanDecoding(s[i-1], s[i])) cur += prePre;
    
                if (cur == 0) return 0;
    
                prePre = pre;
                pre = cur;
            }
    
            return pre;
        }
    
        private bool CanDecoding(char c)
        {
            if (c == '0') return false;
            return true;
        }
    
        private bool CanDecoding(char char1, char char2)
        {
            if (char1 == '1' && '0' <= char2 && char2 <= '9') return true;
            if (char1 == '2' && '0' <= char2 && char2 <= '6') return true;
    
            return false;
        }
    }
    

Log in to reply
 

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