1625. 最小字典序字串

思路

每次可以做的操作:

1. 將奇數位的數字加上 a % 10
2. 或是向右輪轉 b 位 由於數據規模很小，可以暴力搜索出所有可能的情況求解，(當然也可以用數學推導公式加速)。

模擬題目敘述便能求解。

程式碼

class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.length();
        unordered_map<string, bool> umap;
        string res = s;
        auto dfs = [&](this auto&&dfs, string cur) {
            if(umap.find(cur) != umap.end()) return; // 終止條件, 已經搜索過。
            umap[cur] = true;
            // 輪轉
            string next = cur.substr(b) + cur.substr(0, b);
            res = min(res, next);
            dfs(next);
            // 置換
            next = cur;
            for(int i = 1; i < n; i += 2) {
                next[i] = (((next[i] - '0') + a) % 10) + '0';
            }
            res = min(res, next);
            dfs(next);
        };
        dfs(res);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n)$