Lexicographically Smallest String After Applying Operations LeetCode solution in Python

1
"""
2
w: BFS
3
h: for each possible number (node), we have two possible operations (add, rotate)
4
    it seems to be a 2^100 possible number, however, note:
5
    1) add a to number of odd index, we will get to the same number after 10 rounds of add
6
    2) s has even length, if b is odd, we can get the same number after n round
7
    3) for each shift, we would get different number at even index in 10 rounds
8

9
    so we would have 10 * n * 10 number at most, then we can use BFS + memo
10
"""
11

12
import collections
13

14

15
class Solution:
16
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
17
        seen = set()
18
        deque = collections.deque([s])
19

20
        while deque:
21
            # print(deque)
22
            curr = deque.popleft()
23
            seen.add(curr)
24

25
            # 1.add
26
            ad = self.add_(curr, a)
27
            if ad not in seen:
28
                deque.append(ad)
29
                seen.add(ad)
30

31
            # 2. rotate:
32
            ro = self.rotate_(curr, b)
33
            if ro not in seen:
34
                deque.append(ro)
35
                seen.add(ro)
36

37
        return min(seen)
38

39
    def add_(self, s, a):
40
        res = ""
41
        for idx, i in enumerate(s):
42
            if idx % 2 == 1:
43
                num = (int(i) + a) % 10
44
                res += str(num)
45
            else:
46
                res += i
47

48
        return res
49

50
    def rotate_(self, s, b):
51
        idx = len(s) - b
52
        res = s[idx:] + s[0:idx]
53
        return res