[Python 3] DP bottom up
Take 22223 for an example. \n\n2: a\n2+2: 1st a plus another a gives aa, and connecting two 2s gives b. Total number of interpretations doubled.\n22+2: aa and b
Take 22223 for an example. \n\n2: `a`\n2+2: 1st `a` plus another `a` gives `aa`, and connecting two 2s gives `b`. Total number of interpretations doubled.\n22+2: `aa` and `b` from previous index appending another `a` gives `aaa` and `ba`; connecting the last 2 with the 2nd gives `ab`; and connecting all 3 2s gives `c`. Total number of interpretations doubled.\n222+2: since `maximum connectable` 2s == 3, the additional interpretations it brings are:\n\t\tinterpreations for 2 + 222 (`c`)\n\t\tinterpretations for 22 + 22 (`b`)\n\t\tinterpretations for 222 + 2 (`a`)\n2222+3: 3 is a different digit to 2, it does not change the number of interpretations.\n\nFor digits 7 and 9, `maximum connectable` == 4.\n\nState transition:\n```\nif digit[i] != digit[i-1]:\n\tdp[i] = dp[i - 1]\nelse:\n\tif connected <= max_connectable:\n\t\tdp[i] = dp[i - 1] * 2\n\telse:\n\t\tdp[i] += dp[i - j] for j in range(1 to max_connectable inclusively)\n```\n\n```\nclass Solution:\n    def countTexts(self, pressedKeys: str) -> int:\n        n = len(pressedKeys)\n        mod = 1_000_000_007\n        \n        dp = [0] * n\n        dp[0] = 1\n        cnt = 1\n        \n        for i in range(1, n):\n            if pressedKeys[i] != pressedKeys[i - 1]:\n                dp[i] = dp[i - 1]\n                cnt = 1\n            else:\n                cnt += 1\n                if pressedKeys[i] != \'7\' and pressedKeys[i] != \'9\':\n                    if cnt <= 3:\n                        dp[i] = dp[i - 1] * 2 % mod\n                    else:\n                        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod\n                else:\n                    if cnt <= 4:\n                        dp[i] = dp[i - 1] * 2 % mod\n                    else:\n                        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4]) % mod\n        return dp[-1]\n```\n\nA prefix sum can provide minor acceleration.\n\n```\nclass Solution:\n    def countTexts(self, pressedKeys: str) -> int:\n        n = len(pressedKeys)\n        mod = 1_000_000_007\n        \n        dp = [0] * n\n        dp[0] = 1\n        cnt = 1\n        _sum = 1\n        \n        for i in range(1, n):\n            if pressedKeys[i] != pressedKeys[i - 1]:\n                dp[i] = dp[i - 1]\n                cnt = 1\n                _sum = dp[i]\n            else:\n                cnt += 1\n                if pressedKeys[i] != \'7\' and pressedKeys[i] != \'9\':\n                    if cnt <= 3:\n                        dp[i] = dp[i - 1] * 2 % mod\n                        _sum += dp[i]\n                    else:\n                        dp[i] = _sum % mod\n                        _sum = _sum + dp[i] - dp[i - 3]\n                else:\n                    if cnt <= 4:\n                        dp[i] = dp[i - 1] * 2 % mod\n                        if cnt < 4:\n                            _sum += dp[i]\n                        else:\n                            _sum = _sum + dp[i] - dp[i - 3]\n                    else:\n                        dp[i] = (_sum + dp[i - 4]) % mod\n                        _sum = _sum + dp[i] - dp[i - 3]\n        return dp[-1]\n```
['Dynamic Programming']