O(N) DP with memoization
IntuitionBreak problem down into clusters of single numbers.Use dynamic programming with memoization to avoid repeated calculations for the # of combinatiosn pe
# Intuition
Break problem down into clusters of single numbers.

Use dynamic programming with memoization to avoid repeated calculations for the # of combinatiosn per number.

# Approach
Iterate through the string, until the number is different than last.  The difference in indices is the length of the. 

Use count() with dynamic programming to determine the # of combinations for this character.  Pass the number of characters to the count() routine, along with the max numbers per letter (4 for '7' and '9', 3 for all others) 

Call count() recursively until the number of letters left is 0.  This is a single combination, so return 1.  In the DP step, we add up all combinations for using 1, 2, 3 and possibly 4 chars. 

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(N).  Although it seems the count() routine should make this non-linear, since, with memoization we only have to calculate count(k) once for some k.  Since k is the length of the number string, this is never greater than N total. So O(N + k) = O(N)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(N) for memoization

# Code
```python3 []
class Solution:
    def count(self, lettersLeft, mx):
        if lettersLeft == 0:
            return 1
        #print(f"lettersLeft={lettersLeft}")
        idx = (lettersLeft, mx)
        if idx in self.memo:
            return self.memo[idx]
        cnt = 0
        for i in range(1, 1+min(lettersLeft, mx)):
            cnt += self.count(lettersLeft-i, mx)
        self.memo[idx] = cnt
        return cnt

    def countTexts(self, pressedKeys: str) -> int:
        self.memo = dict()
        N = len(pressedKeys)
        i = 0
        r = 1
        while i < N:
            n = 0
            j = i
            c = pressedKeys[j]
            while j < N and pressedKeys[j] == c:
                j += 1
            mx = 3
            if c in ('7', '9'):
                mx = 4
            cnt = self.count(j-i, mx)
            #print(f"i={i} cnt={cnt}")
            r = r * cnt
            i = j
        #print(f"{self.memo}")
        return r % (10**9 + 7)

        
```
['Python3']