1625. Lexicographically Smallest String After Applying Operations

題目

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.

You can apply either of the following two operations any number of times and in any order on s:

• Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5, s becomes "3951".

• Rotate s to the right by b positions. For example, if s = "3456" and b = 1, s becomes "6345".

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "0158" is lexicographically smaller than "0190" because the first position they differ is at the third letter, and '5' comes before '9'.

題目連結

思路

此題可以利用類似深度優先搜尋 (DFS) 的方式來找出所有可能的組合，並且用一個 set 來維護，最後找出當中最小的值即可滿足題目要求。

首先需要定義題目所需的兩種操作，包含 add：

def add(s):
    sList = list(s)

    for i, char in enumerate(sList):
        if i % 2 == 1:
            sList[i] = str((int(char) + a) % 10)

    return "".join(sList)

以及 rotate：

def rotate(s):
    return s[n-b:] + s[:n-b]

最後利用優先搜尋以遞迴的方式把所有的組合找出來，直到回到重複的值即完成搜尋：

def search(s):
    if s in allSeq:
        return

    allSeq.add(s)
    search(add(s))
    search(rotate(s))

Full Code

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        allSeq = set()
        n = len(s)

        def add(s):
            sList = list(s)

            for i, char in enumerate(sList):
                if i % 2 == 1:
                    sList[i] = str((int(char) + a) % 10)

            return "".join(sList)

        def rotate(s):
            return s[n-b:] + s[:n-b]

        def search(s):
            if s in allSeq:
                return

            allSeq.add(s)
            search(add(s))
            search(rotate(s))

        search(s)

        return sorted(allSeq)[0]