Lexicographically Smallest String After Applying Operations

'''
Logic:
We will apply BFS.The time complexity allows us to see all the possibility but
we will also use a map so that we won't repeat
the same output.
for every input,If it is present in map,means already visited this string.
if not in map,compare it with the answer string.
Now,two modification to do,add a to every odd position and send for bfs.
second,rotate the string by b and send for bfs.
'''
def _add(s,a):
    ans=""
    for i in range(0,len(s)):
        if i%2==0:
            ans+=s[i]
            continue
        ans+=str((int(s[i])+a)%10)
    return ans

def _rot(s,b):
    return s[len(s)-b:]+ s[0:len(s)-b]

def bfs(s,a,b,dict,ans):
    ans[0]=min(ans[0],s)
    if s in dict.keys():
        return
    dict[s]=1
    new_s=_add(s,a)
    rot_s=_rot(s,b)
    bfs(new_s,a,b,dict,ans)
    bfs(rot_s,a,b,dict,ans)

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        dict={}
        ans=[s]
        bfs(s,a,b,dict,ans)
        return ans[0]