[LeetCode] Decode Ways

Problem: A message containing letters from A-Z is being encoded to numbers using the following mapping:

• 'A' -> 1
• 'B' -> 2
• ...
• 'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example:

Input: s = "15"
Output: 2
Explanation: "15" could be decoded as "AE" (1 5) or "O" (15).

Approach: Looks like fibonacci problem. Use DP.

Implementation in C#:

        public static int NumDecodings(string s)

        {

            if (string.IsNullOrWhiteSpace(s))

            {

                return 0;

            }

            if (s[0] == '0')

            {

                return 0;

            }

            int[] count = new int[s.Length + 1];

            count[0] = 1;

            count[1] = 1;

            for (int i = 2; i <= s.Length; ++i)

            {

                count[i] = 0;

                if (s[i - 1] > '0')

                {

                    count[i] = count[i - 1];

                }

                if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))

                {

                    count[i] += count[i - 2];

                }

            }

            return count[s.Length];

        }

Complexity: O(n)