<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>

class Solution:
    def __init__(self) -> None:
        self.dial_chars = ("","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz")
        self.key_counts = {}
        self.memo = {}
        self.n_mod = pow(10, 9) + 7
        return
    def countKeyPresses(self, key_presses: str) -> None:
        for i in key_presses:
            if i not in self.key_counts:
                self.key_counts[i] = 1
                continue
            self.key_counts[i] += 1
        return
    # def dfsWays(self, key_items: List, keys_params: List, idx_n: int, key_prev: str, key_presses: int) -> int:
    #     keypad_idx_min, keypad_idx_max = keys_params[0], keys_params[1]
    #     if (idx_n, key_presses) in self.memo:
    #         return self.memo[(idx_n, key_presses)]
    #     if idx_n not in range(keypad_idx_min, keypad_idx_max):
    #         if idx_n == keypad_idx_max:
    #             return 1
    #         return 0
    #     ans = 0
    #     #default recurrence relation
    #     if key_items[idx_n] == key_prev:
    #         if (key_presses + 1) in range(len(self.dial_chars[int(key_items[idx_n]) - 1])):
    #             ans += self.dfsWays(key_items, keys_params, idx_n + 1, key_prev, key_presses + 1)
    #     ans += self.dfsWays(key_items, keys_params, idx_n + 1, key_items[idx_n], 0)
    #     self.memo[(idx_n, key_presses)] = ans
    #     return ans
    def dfsWays(self, key_itms: List, idx_n: int) -> int:
        if idx_n in self.memo:
            return self.memo[idx_n]
        if idx_n not in range(len(key_itms)):
            return 1 if idx_n == len(key_itms) else 0
        ans = 0
        val_range = len(self.dial_chars[int(key_itms[idx_n]) - 1])
        for i in range(1, val_range + 1):
            # if idx_n + i not in range(len(key_itms)):
            #     break
            # if key_itms[idx_n + i] != key_itms:
            #     ans += self.dfsWays(key_itms, idx_n + i)
            #     break
            if idx_n + i not in range(len(key_itms)) or key_itms[idx_n + i] != key_itms[idx_n]:
                ans += (self.dfsWays(key_itms, idx_n + i) % self.n_mod)
                break
            ans += (self.dfsWays(key_itms, idx_n + i) % self.n_mod)
        self.memo[idx_n] = ans
        return ans
    def countTexts(self, pressedKeys: str) -> int:
        #key_items = list(dict)
        #return self.dfsWays(key_items, [0, len(key_items)], 0, "", 0)
        # rand_test = RandomInputGen(pow(10,5), 2, 9)
        # test_data = ''.join(rand_test.genRandomInput())
        # print(test_data)
        # TODO restore most recent:
        # return self.dfsWays(pressedKeys, [0, len(pressedKeys)], 0, "", 0) % self.n_mod
        return self.dfsWays(pressedKeys, 0) % self.n_mod

1361