10 line dp python, O(n) | O(1), beat 100% | 100%  A easy bottom-up
\nclass Solution(object):\n    def countTexts(self, keys):\n        dic = {\'2\': 3, \'3\': 3, \'4\':3, \'5\':3, \'6\':3, \'7\':4, \'8\': 3, \'9\':4 } # diction
```\nclass Solution(object):\n    def countTexts(self, keys):\n        dic = {\'2\': 3, \'3\': 3, \'4\':3, \'5\':3, \'6\':3, \'7\':4, \'8\': 3, \'9\':4 } # dictionary!\n        \n        # e.g  dp means all possibilities ending now. 4 status totaly dp2 means we quickly press same num for 2 times. (33)-->e\n        dp1, dp2, dp3, dp4 = 1, 0, 0, 0   # assuming we passed first key, dp1 is 1\n\t\t\n        for i in range(1, len(keys)):\n            if keys[i] == keys[i-1]: # if same with before, this is how we inherit\n                dp1, dp2, dp3, dp4 = (dp1 + dp2 + dp3 + dp4) % (10**9+7), dp1, dp2, 0 if dic[keys[i]] == 3 else dp3\n            else: # and when not same, this is how we inherit\n                dp1, dp2, dp3, dp4 = (dp1 + dp2 + dp3 + dp4) % (10**9+7), 0, 0, 0\n\t\t\t\t\n        return (dp1 + dp2 + dp3 + dp4) % (10**9+7)\n\t\t\n\t\t\nActually the status is pretty clear. There are 3-4 status when ending at each index among the keys, and status transfer is also clear to see. \n```\n\n\n\n\n```\n#Also here\'s top-down dp ( = dfs + memo). Same time complexity, O(N) space. \nclass Solution:\n    def countTexts(self, keys: str) -> int:\n        \n        dic = {\'2\': 3, \'3\': 3, \'4\':3, \'5\':3, \'6\':3, \'7\':4, \'8\': 3, \'9\':4 }\n\n        @lru_cache(None)\n        def dp(i, acc):\n            if i == 0:\n                if acc == 1:\n                    return 1\n                return 0\n\n            if acc == 1:\n                return sum([ dp(i-1, k) for k in range(1, dic[keys[i-1]] +1) ]) % (10**9+7)\n            \n            if keys[i] == keys[i-1]:\n                return dp(i-1, acc-1)\n            \n            return 0\n        \n        return sum([ dp(len(keys)-1, k) for k in range(1, dic[keys[-1]]+1) ]) % (10**9+7)\n    ```\n\t\n\n\t
['Dynamic Programming', 'Python']