Decode Ways
Medium About 20 min Free, no account needed
How many letter strings could this digit string encode?
The brief
Letters map to numbers (A=1 ... Z=26). Given a digit string s, count the
ways to decode it. A 0 decodes only as the tail of 10 or 20.
The obvious approach recurses on one- and two-digit takes, 2^n on a string of 80 ones (the hidden test), whose answer is a 17-digit Fibonacci number. You need to avoid recomputing the same suffix over and over, O(n).
Starter code
using System;
public class Solution
{
// TODO: return the number of decodings of the digit string.
public long NumDecodings(string s)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Do these first
Related katas
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?
- House Robber II (Circular Street) Medium Free The street is a circle now - the first and last houses are neighbors.
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.