Backtrack Solution using DFS || Intuitive || Easy to Understand
Intuition\nWe can use backtracking to solve this problem\n\n# Approach\nThe goal is to find the lexicographically smallest string that can be obtained by perfor
# Intuition\nWe can use backtracking to solve this problem\n\n# Approach\nThe goal is to find the lexicographically smallest string that can be obtained by performing two types of operations on an initial string s:\n\n- Add Operation: For every character at an odd index in the string, add a given integer a to its digit value (modulo 10).\nRotate Operation: Rotate the string to the right by a given integer b positions.\n- To solve this problem, we employ a backtracking approach with memoization to explore all possible transformations of the string. Here\u2019s a step-by-step breakdown of the approach:\n\n1. Initialize Result and Visited Set\nResult Initialization: We start by initializing the result list res with the original string s. This will store the lexicographically smallest string found during the exploration.\nVisited Set: A set visit is used to keep track of all strings that have been seen so far to avoid redundant processing.\n2. Define the Backtracking Function\nThe backtracking function backtrack is defined to explore all possible transformations of the string. The function works as follows:\n\n- Base Case: If the current string s has already been visited, the function returns immediately to avoid redundant work.\n- Add String Transformation:\n - A new string tmpAd is created by performing the add operation on every character at an odd index.\n- If the new string tmpAd is lexicographically smaller than the current result in res[0], update res[0] with tmpAd.\n- Recursively call backtrack on the new string tmpAd to continue exploring further transformations.\n- Rotate String Transformation:\n- A new string s is created by rotating the original string to the right by b positions.\n- If the new rotated string s is lexicographically smaller than the current result in res[0], update res[0] with the rotated string.\n- Recursively call backtrack on the rotated string s to continue exploring further transformations.\n3. Start the Backtracking Process\nThe backtracking process is initiated by calling backtrack with the original string s, and the given values a and b.\n\nFinally, the smallest lexicographically string found is returned from res[0].\n# Complexity\n- Time complexity:\n$$ O(n\u22C510^n)) $$\n\n- Space complexity:\n$$ O(10^n)) $$\n\n# Code\n```\nres = [s] # Result\nvisit = set() # Already seen string\ndef backtrack(s, add, rotate):\n    # Base Case\n    if s in visit:\n        return\n    \n    visit.add(s)\n    # Creating Add String\n    tmpAd = \'\' \n    # Performing add operation on string\n    for i in range(len(s)):\n        if i % 2:\n            tmpAd += str((int(s[i]) + add) % 10)\n        else:\n            tmpAd += s[i]\n    # Updatin res[0] if lexicographically smaller\n    if tmpAd < res[0]:\n        res[0] = tmpAd\n    # Recursively Performing both operation again on add ng\n    backtrack(tmpAd, add, rotate)\n    # Performing rotate operation on the original string\n    s = s[rotate:] + s[:rotate]\n    # Updatin res[0] if lexicographically smaller\n    if s < res[0]:\n        res[0] = s\n    # Recursively Performing both operation again on add ng\n    backtrack(s, add, rotate)\n    return\n\nbacktrack(s, a, b)\nreturn res[0]\n```
['Python3']