Python DFS with high-level explanation
The key insight for me was that you cant easily confirm any one step will lead to a smaller number, nor if given the smallest result that it is indeed the small
The key insight for me was that you cant easily confirm any one step will lead to a smaller number, nor if given the smallest result that it is indeed the smallest possible. So you have to search the whole space of possible values "s" can take using some search algorithm. Think of each possible value string "s" can take as a unique vertex in a graph and the two functions (`add` and `rotate`) as two edges leading out of each vertex. The nature of the functions then don\'t matter and should conceptually just be thought of as black boxes leading you to another vertex.\n\nSo, you\'re really just seaching a graph for the smallest element. To prevent loops just make sure you don\'t continue searching if you have already seen a number (i.e. already visited a vertex).\n\n```\nclass Solution:\n    def __init__(self):\n        self.smallest = float("inf")\n        self.seen = {}\n    \n    def rotate(self, s, b):\n        s = [char for char in s]\n        def reverse_segment(start, end):\n            end -= 1\n            while start < end:\n                s[start], s[end] = s[end], s[start]\n                start += 1\n                end -= 1\n        rotations = b % len(s)\n        reverse_segment(0, len(s))\n        reverse_segment(0, rotations)\n        reverse_segment(rotations, len(s))\n        return "".join(s) \n    \n    def add_one(self, char, a):\n        return str((int(char)+a) % 10)\n    \n    def add(self, s, a):\n        s = [char for char in s]\n        for idx in range(len(s)):\n            if idx % 2 != 0:\n                s[idx] = self.add_one(s[idx], a)\n        return "".join(s)\n    \n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        if self.smallest == float("inf"):\n            self.smallest = s        \n        if int(s) < int(self.smallest):\n            self.smallest = s\n        if s in self.seen:\n            return\n        self.seen[s] = True\n        self.findLexSmallestString(self.rotate(s,b), a, b)\n        self.findLexSmallestString(self.add(s,a), a, b)\n        return self.smallest\n````
['Python', 'Python3']