[Python]O(N) dp, easy to understand with explanation
Observation and intuition\n"return the total number of possible text messages Alice could have sent" means that this is a counting-number-of-ways problem, which
**Observation and intuition**\n"return the total number of possible text messages Alice could have sent" means that this is a counting-number-of-ways problem, which is a signal of trying dynamic programming.\n\nLet\'s have some simple observations trying to get some intuition about the recurrence relations:\n1. if S = "2", then we only have one option: (2)\n2. if S = "23", then we only have one option: (2)(3)\n3. if S = "22", then we have two options: (2)(2), (22)\n4. if S = "223", then we have two options: (2)(2)(3), (22)(3)\n5. if S = "222", then we have four options: (2)(2)(2), (22)(2), (2)(22), (222)\n\nNote that ***more options emerge because we can combine the same letters together***, this is the main fact that we should utilize to break down this problem.\n\n\n**Explanation:**\nWhen we traverse the string S and we are at the index i, there are 3 (or 4 for "7" and "9") cases to be considered for the letter at index i:\n1. consider that letter separately, so combination[i] = combination[i - 1]\n2. if the two last letters stopping at index i are the same, we have an option to combine them, then combination[i] += combination[i - 2]\n3. if the three last letters stopping at index i are the same, we have an option to combine them, then combination[i] += combination[i - 3]\n4. if the four last letters (for "7" and "9") stopping at index i are the same, we have an option to combine them, then combination[i] += combination[i - 4]\n\nTake "2222" as an example and we are at the last "2":\ncase 1: "222(2)", combination["2222"] = combination["222"]\ncase 2: "22(22)", combination["2222"] += combination["22"]\ncase 3: "2(222)", combination["2222"] += combination["2"]\n\n```\nclass Solution:\n    def countTexts(self, S: str) -> int:\n        \n        mod = 10 ** 9 + 7\n        \n        dp = [0] * (len(S) + 1)\n        dp[0] = 1\n        for i in range(1, len(S) + 1):\n            dp[i] = dp[i - 1]\n            if i - 2 >= 0 and S[i-1] == S[i-2]:\n                dp[i] += dp[i - 2]\n            if i - 3 >= 0 and S[i-1] == S[i-2] and S[i-1] == S[i-3]:\n                dp[i] += dp[i - 3]\n                \n            if S[i-1] in {"7", "9"}:\n                if i - 4 >= 0 and S[i-1] == S[i-2] and S[i-1] == S[i-3] and S[i-1] == S[i-4]:\n                    dp[i] += dp[i - 4]\n            dp[i] %= mod\n            \n        return dp[-1] % mod
['Dynamic Programming']