[Python3] DP | Time Complexity O(n^2)
Approach\n Describe your approach to solving the problem. \nNote that any valid string transformed from s is able to be reached within 2 * 9 add and n + 1 rotat
# Approach\n<!-- Describe your approach to solving the problem. -->\nNote that any valid string transformed from `s` is able to be reached within `2 * 9` add and `n + 1` rotate operations, which means that there are at most `2 * 9 * (n + 1)` states needed to reach to optimum solution. \n\nIt is one of the most reliable method to iterate all these states with DFS or BFS. Despite using DP here, I failed to prove whether or not the problem has optimum substructure property. My code could be false when the test cases get stronger and larger.\n\n\n# Complexity\n- Time complexity: $O(n^2)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n^2)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python\nclass Solution:\n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        n = len(s)\n        N = 20\n        M = n + 2\n        f = [[""] * N for _ in range(M)]\n\n        def add(s, a):\n            res = ""\n            for i, d in enumerate(s):\n                if i & 1:\n                    res += chr((ord(d) - ord(\'0\') + a) % 10 + ord(\'0\'))\n                else:\n                    res += d\n            return res\n        \n        def rotate(s, b):\n            return s[b : ] + s[0 : b]\n\n        ans = s\n        f[0][0] = s\n\n        for i in range(1, N):\n            f[0][i] = add(f[0][i - 1], a)\n            ans = min(ans, f[0][i])\n        for i in range(1, M):\n            f[i][0] = rotate(f[i - 1][0], b)\n            ans = min(ans, f[i][0])\n        \n        for i in range(1, M):\n            for j in range(1, N):\n                s1 = add(f[i][j - 1], a)\n                s2 = rotate(f[i - 1][j], b)\n                f[i][j] = min(s1, s2)\n                ans = min(ans, f[i][j])\n                \n        return ans\n\n```
['Python3']