I was trying to write TRIE for mnemonic words and DFS that tree with phone number. And I have failed. After that, I wrote just 2-D dimensional dynamic programming solution. DP[i] [j] is minimal number of words to memorize substring [i;j]. And I got success. Used Python. Just input, not stdin from sys.