Starting from the front, using recursion, I got 0.12s..stcheung wrote:I got TLE at first too (it's unfortunate that time limit is now 10 second instead of the previous 30 second). I just got AC using 0.5 second by the stack approach. Basically just start at the end of the string, and whenever you see one of the C, D, E, or I, check if stack has at least 2 correct sentences. Let's say the current char is C, and the stack has 2 correct sentences on the top, then they can all be combined into one correct sentence and pushed onto the stack. If the stack doesn't have 2 correct sentences on the top, then you can immediately judge the string as incorrect.
Another optimization is to take out the N.
This is a very simple parsing question. There is no need for branching, so no need for DP.
Realise that
If X is a sentence and Y is a sentence, XY is NOT a sentence.
This effectively tells you how the recursion should go.