[Python] process every char with DFS
\n"""\nProcess each character by DFS with recursion.\n\nTC: (T)\nSC: (N+T)\n"""\nclass Solution:\n    def lengthAfterTransformations(self, s: str, t: int) -> in
```\n"""\nProcess each character by DFS with recursion.\n\nTC: (T)\nSC: (N+T)\n"""\nclass Solution:\n    def lengthAfterTransformations(self, s: str, t: int) -> int:\n\n        @cache\n        def dfs(ch, t):\n            d = ord(\'z\') - ord(ch)  # how many steps to became `z`\n            if t <= d:\n                return 1\n\n            return (dfs(\'a\', t - d - 1) + dfs(\'b\', t - d - 1)) % (10**9 + 7)\n\n        r = 0\n        for ch in s:\n            r += dfs(ch, t)\n\n        dfs.cache_clear()  # clear after each test case to prevent MLE\n        return r % (10**9 + 7)\n```
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'Python']