Count decodings of a digit string

Q: Count decodings of a digit string

This question evaluates algorithmic problem-solving focused on dynamic programming, string processing, and correct handling of invalid prefixes and zeros in combinatorial decodings, categorized under Coding & Algorithms.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a non-empty digit string s consisting of characters '0'–'9' and a mapping where 1->'a', 2->'b', ..., 26->'z'. Return the number of valid ways to decode s. Note that '0' cannot be decoded alone and is only valid as part of '10' or '20'. Provide an O(n) time solution, explain how to handle zeros and invalid prefixes, analyze time and space complexity, and implement in C++. Optionally include a space-optimized variant.

Count decodings of a digit string

Overview

Comments (0)