<p>Alice is texting Bob using her phone. The <strong>mapping</strong> of digits to letters is shown in the figure below.</p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png" style="width: 200px; height: 162px;" />
<p>In order to <strong>add</strong> a letter, Alice has to <strong>press</strong> the key of the corresponding digit <code>i</code> times, where <code>i</code> is the position of the letter in the key.</p>

<ul>
	<li>For example, to add the letter <code>&#39;s&#39;</code>, Alice has to press <code>&#39;7&#39;</code> four times. Similarly, to add the letter <code>&#39;k&#39;</code>, Alice has to press <code>&#39;5&#39;</code> twice.</li>
	<li>Note that the digits <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code> do not map to any letters, so Alice <strong>does not</strong> use them.</li>
</ul>

<p>However, due to an error in transmission, Bob did not receive Alice&#39;s text message but received a <strong>string of pressed keys</strong> instead.</p>

<ul>
	<li>For example, when Alice sent the message <code>&quot;bob&quot;</code>, Bob received the string <code>&quot;2266622&quot;</code>.</li>
</ul>

<p>Given a string <code>pressedKeys</code> representing the string received by Bob, return <em>the <strong>total number of possible text messages</strong> Alice could have sent</em>.</p>

<p>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> pressedKeys = &quot;22233&quot;
<strong>Output:</strong> 8
<strong>Explanation:</strong>
The possible text messages Alice could have sent are:
&quot;aaadd&quot;, &quot;abdd&quot;, &quot;badd&quot;, &quot;cdd&quot;, &quot;aaae&quot;, &quot;abe&quot;, &quot;bae&quot;, and &quot;ce&quot;.
Since there are 8 possible messages, we return 8.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pressedKeys = &quot;222222222222222222222222222222222222&quot;
<strong>Output:</strong> 82876089
<strong>Explanation:</strong>
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 10<sup>9</sup> + 7, we return 2082876103 % (10<sup>9</sup> + 7) = 82876089.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= pressedKeys.length &lt;= 10<sup>5</sup></code></li>
	<li><code>pressedKeys</code> only consists of digits from <code>&#39;2&#39;</code> - <code>&#39;9&#39;</code>.</li>
</ul>

'''
Approach: Dynamic programming decode ways


Each chunk of numbers represents a potential decoding

222

number of ways to decode it:

aaa
ab
ba
c

33

dd
e

Therefore, need to first break by changing characters
222 | 33

a: all substrings of len 1
b: all substrings of len 2
c: all substrings of len 3

All substrings = O(n^2)



number of ways to decode = prod(number of ways to decode all same char subsets)

         222 
   /      |      \
a22      b2      c
  /\      |
aa2 ab    ba

number of ways to decode i to i + 3 non inclusive



Algo:

Get list of all substrings containing only 1 unique character

prod = 1
For substring in above list:
    prod *= number of ways to decode substring

return prod % mod_number


def number_ways_to_decode_substring(i: int, s: String) -> int:

    if i == len(s):
        return 1 # found a valid decoding, end serach

    res = number_ways_to_decode_substring(i + 1, s)

    # valid means second part (i + x) is not greater than len(s)

    if s[i:i+2] not oob: # 2 char solution
        res += number_ways_to_decode_substring(i + 2, s)

    if s[i:i+3] not oob: # 3 char solution
        res += number_ways_to_decode_substring

    if s[i:i+4] not oob: # 4 char solution - only for 9
        res += number_ways_to_decode_substring

    return res


'''



class Solution:
    def countTexts(self, pressedKeys: str) -> int:


        memo = {}

        def dp(i: int, s: str) -> int:



            if i == len(s):
                return 1 # found a valid decoding, end serach


            if (i, s) not in memo:

                res = dp(i + 1, s)

                # valid means second part (i + x) is not greater than len(s)


                if i + 2 <= len(s): # 2 char solution
                    res += dp(i + 2, s)

                if i + 3 <= len(s): # 3 char solution
                    res += dp(i + 3, s)

                if s[i] in ['7','9'] and i + 4 <= len(s): # 4 char solution - only for 9
                    res += dp(i + 4, s)

                memo[(i, s)] = res % (10 ** 9 + 7)

            return memo[(i, s)] 



        bt_list = []

        l = 0
        for r in range(len(pressedKeys)):
            if pressedKeys[l] == pressedKeys[r]:
                continue
            else:
                bt_list.append(pressedKeys[l:r])
                l = r
        bt_list.append(pressedKeys[l:len(pressedKeys)])

        # print(bt_list)

        prod = 1
        for same_char_substring in bt_list:
            memo = {}
            prod *= dp(0, same_char_substring)
        return prod % (10 ** 9 + 7)






68408