Codeforces Round #764 Masha-forgetful Solution (Java/C++)

Solution:

Trie + DP。

First, any number greater than 3 can be represented as the sum of 2s and 3s. So we have each of our segments of length either 2 or 3.

Then for the original n phone numbers, we add all substrings of length 2 and length 3 into the dictionary tree to be checked. The Trie will record the index and position of this substring.

Next is the DP part. dp[i] represents the solution for the first i digits. The slightly unusual thing here is that dp[i] is not a number, but an object. If dp[i]=null there is no solution.
So there are two choices for the value of dp[i]: 1. If dp[i-2] is not empty, and the letters i-1 and i can be found in the Trie, then the value of dp[i] is the Trie recorded value. 2. Similarly, we consider 3 letters to look up in the Trie, and check the value of dp[i-3]. If neither works, then dp[i] is empty.

So we only need to calculate the information of each segment from m to 1 according to the records of the Trie and DP.

Code:

Java

C++