Simple C# O(1) Space O(n) Runtime with explanation.


  • 0
    V

    Explanation -

    To decode n digits -
    We can decode n-1 digits and decode the last digit by itself IF last digits is valid (digit >=1 and digit <= 9).
    OR
    We decode n-2 digits and decode the last two digits as a whole if the last two digits are valid (digits >=10 and digits <= 26)

    We can use recursion to start with n and go down to 1 or we can build up the solution using a for loop from 1 to n.

    No need to save all the results decoding n digits needs results from previous two digits only (decoding n-1 and decoding n-2)

    public class Solution {
        public int NumDecodings(string s) 
        {
            if(string.IsNullOrWhiteSpace(s))
            {
                return 0;
            }
            
            int result_2 = 0, result_1 = 1;
            int result = 0;
            
            for(int i=1; i<= s.Length; i++)
            {
                result = 0;
                
                int code = s[i-1] - '0';
                if(code >=1 && code<=9)
                {
                    result+= result_1;
                }
                
                if(i >= 2)
                {
                    code = Int32.Parse(s.Substring(i-2, 2));
                    if(code >= 10 && code <= 26)
                    {
                        result+= result_2;
                    }
                }
                
                result_2 = result_1;
                result_1 = result;
            }
            
            return result;
        }
    }
    

Log in to reply
 

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