Python | Top Down DP | Time: O(4*N) | Easy Understanding
The result is solely impacted by the following four digits at index i.\nNote that using MOD everywhere can save you a lot of time!\n\nTime: O(4*n)\n\npy\nclass 
The result is solely impacted by the following four digits at index i.\nNote that using MOD everywhere can save you a lot of time!\n\nTime: O(4*n)\n\n``` py\nclass Solution:\n    def countTexts(self, A: str) -> int:\n        mp = set(["2", "22", "222",\n                  "3", "33", "333",\n                  \'4\', \'44\', \'444\',\n                  \'5\', \'55\', \'555\',\n                  \'6\', \'66\', \'666\',\n                  \'7\', \'77\', \'777\', \'7777\', \n                  \'8\', \'88\', \'888\', \n                  \'9\', \'99\', \'999\', \'9999\'])\n        MOD = 10**9+7\n        \n        @cache\n        def dp(i):\n            if i>=len(A): return 1\n            ans = 0\n            if i+1<=len(A) and A[i:i+1] in mp: ans += dp(i+1)%MOD\n            if i+2<=len(A) and A[i:i+2] in mp: ans += dp(i+2)%MOD\n            if i+3<=len(A) and A[i:i+3] in mp: ans += dp(i+3)%MOD\n            if i+4<=len(A) and A[i:i+4] in mp: ans += dp(i+4)%MOD\n            return ans%MOD\n        \n        return dp(0)%MOD\n```
['Dynamic Programming', 'Recursion', 'Python']