A very nice puzzle. I converged pretty quickly towards a TRIE (the first option that came into my mind actually).
I started by implementing a stack-based traversal as I was thinking that recursion would be too slow. Turned out my implementation was way too slow
I used a naive caching and it really didn't save time.
Switching to a decent cache allowed me to use the simplest recursion and implied DFS, with the DP boosting performance to millisecond range
After all dust settled down, it allowed also for a nifty golfing experience
The validation test cases are nice, and their names mostly imply their content. Nice selection of edge cases.
nice puzzle. If you are stuck on the long test-case, don't give up hope