[Java/Python 3] BFS and DFS w/ brief explanation and analysis.
Method 1: BFS\n\nQ & A:\n\nQ1: When does the queue becomes empty? I mean, how can we be sure that the BFS dosen\'t go into infinite loop?\nA1: When all possible
**Method 1: BFS**\n\n**Q & A:**\n\nQ1: When does the queue becomes empty? I mean, how can we be sure that the BFS dosen\'t go into infinite loop?\nA1: When all possible strings that created after operations have already been in the set `seen`, no string can be put into queue any more; After that, the queue will deplete sooner or later.\nSince the input string `s` has limited size and each digit has at most 10 options, there are finite strings created during the whole BFS.\n\nQ2:  Why this solution works?\nA2: BFS traverse all possible strings and update the smallest string whenever polling out a string from the Queue. Therefore, the algorithm guarantees to output correct solution.\n\n**End of Q & A**\n\n\n----\n\n\n1. Use a `Queue` / `deque` to hold the strings after applying operations;\n2. Use a `Set` to avoid duplication;\n3. During BFS, for each polled out string, compare it to the currently smallest string and update the smallest  if necessary; apply the 2 operations and put the resulted 2 strings into the `Queue` / `deque` if never seen them before;\n4. The smallest string found after BFS is the solution.\n\n```java\n    public String findLexSmallestString(String s, int a, int b) {\n        int n = s.length();\n        String smallest = s;\n        Queue<String> q = new LinkedList<>();\n        q.offer(s);\n        Set<String> seen = new HashSet<>(q);\n        while (!q.isEmpty()) {\n            String cur = q.poll();\n            if (smallest.compareTo(cur) > 0)\n                smallest = cur;\n            char[] ca = cur.toCharArray();\n            for (int i = 1; i < ca.length; i += 2) // add operation.\n                ca[i] = (char)((ca[i] - \'0\' + a) % 10 + \'0\');\n            String addA = String.valueOf(ca);\n            if (seen.add(addA))\n                q.offer(addA);\n            String rotate = cur.substring(n - b) + cur.substring(0, n - b); // rotation.\n            if (seen.add(rotate))\n                q.offer(rotate);\n        }\n        return smallest;\n    }\n```\n```python\n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        dq, seen, smallest = deque([s]), {s}, s\n        while dq:\n            cur = dq.popleft()\n            if smallest > cur:\n                smallest = cur\n            addA = list(cur)    \n            for i, c in enumerate(addA):\n                if i % 2 == 1:\n                    addA[i] = str((int(c) + a) % 10)\n            addA = \'\'.join(addA)        \n            if addA not in seen:\n                seen.add(addA);\n                dq.append(addA)\n            rotate = cur[-b :] + cur[: -b]\n            if rotate not in seen:\n                seen.add(rotate)\n                dq.append(rotate)\n        return smallest\n```\nIn case you you prefer `list` to `deque`, here  is the `list` version:\n```python\n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        q, seen, smallest = [s], {s}, s\n        while q:\n            new_q = []\n            for cur in q:\n                if smallest > cur:\n                    smallest = cur\n                addA = list(cur)    \n                for i, c in enumerate(addA):\n                    if i % 2 == 1:\n                        addA[i] = str((int(c) + a) % 10)\n                addA = \'\'.join(addA)        \n                if addA not in seen:\n                    seen.add(addA);\n                    new_q.append(addA)\n                rotate = cur[-b :] + cur[: -b]\n                if rotate not in seen:\n                    seen.add(rotate)\n                    new_q.append(rotate)\n            q = new_q    \n        return smallest\n```\n----\n\n**Method 2: DFS**\n\nThe follows are two variants of DFS, use whichever you are comfortable with.\n\nThe ideas behind the codes are similar: \n1. Use a set to avoid duplications, and \n2. Starting from input string, apply the two operations; for each created string, compare it with the previous string to update the smallest string; recurse and repeat the procedure till all possible created strings have been visited.\n\n\n\nvoid/None return type of `dfs()` method\n\n```java\n    private String smallest;\n    public String findLexSmallestString(String s, int a, int b) {\n        smallest = s;\n        dfs(s, a, b, new HashSet<>());\n        return smallest;\n    }\n    private void dfs(String s, int a, int b, Set<String> seen) {\n        if (seen.add(s)) {\n            if (smallest.compareTo(s) > 0) {\n                smallest = s;\n            }\n            char[] ca = s.toCharArray();\n            for (int i = 1; i < ca.length; i += 2) {\n                ca[i] = (char)((ca[i] - \'0\' + a) % 10 + \'0\');\n            }\n            dfs(String.valueOf(ca), a, b, seen);\n            dfs(s.substring(b) + s.substring(0, b), a, b, seen);\n        }\n    }\n```\n```python\n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        \n        def dfs(s: str) -> None:\n            if s not in seen:\n                seen.add(s)\n                self.smallest = min(s, self.smallest)\n                addA = list(s)\n                for i, c in enumerate(addA):\n                    if i % 2 == 1:\n                        addA[i] = str((int(c) + a) % 10)\n                dfs(\'\'.join(addA))\n                dfs(s[b :] + s[: b])\n                \n        self.smallest = s\n        seen = set()\n        dfs(s)\n        return self.smallest\n```\nString return type of `dfs()` method:\n\n```java\n    public String findLexSmallestString(String s, int a, int b) {\n        return dfs(s, a, b, new HashSet<>());\n    }\n    private String dfs(String s, int a, int b, Set<String> seen) {\n        String smallest = s;\n        if (seen.add(s)) {\n            char[] ca = s.toCharArray();\n            for (int i = 1; i < ca.length; i += 2) {\n                ca[i] = (char)((ca[i] - \'0\' + a) % 10 + \'0\');\n            }\n            String addA = dfs(String.valueOf(ca), a, b, seen);\n            String rotate = dfs(s.substring(b) + s.substring(0, b), a, b, seen);\n            for (String candidate : new String[]{addA, rotate}) {\n                if (smallest.compareTo(candidate) > 0) {\n                    smallest = candidate;\n                }\n            }\n        }\n        return smallest;\n    }\n```\n```python\n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        \n        def dfs(s: str) -> str:\n            if s not in seen:\n                seen.add(s)\n                addA = list(s)\n                for i, c in enumerate(addA):\n                    if i % 2 == 1:\n                        addA[i] = str((int(c) + a) % 10)\n                return min(s, dfs(\'\'.join(addA)), dfs(s[b :] + s[: b]))\n            return s    \n                \n        seen = set()\n        return dfs(s)\n```\n\n----\n\n\n**Analysis:**\n\n1. Without rotation, in worst case we have 10 strings due to "add a" operation;\n2. With rotations, for each string in step 1, in worst case we can have `n` new strings, where `n = s.length()`;\n3. For each string in step 2, if `b` is odd, in worst case we can create 10 strings due to "add a" operation; (Note: if `b` is even, then no new strings can be created during this step.)\n\nCombine the above 3 steps, the time and space cost `10 * n * 10`; Therefore, the complexities are as follows:-\n\nTime & space: `O(n * base ^ 2)`, where `n = s.length()`, base = 10.
[]