1625. 执行操作后字典序最小的字符串-526互联

方法：bfs暴力搜索

解题思路

初始化队列\(q\)，若\(q\)不为空，取队首字符串和\(ans\)进行比较，取其中字典序小的字符串，然后队首字符串对于两种操作可以生成两个字符串，将其中未出现过（即未遍历过）的字符串加入\(q\)中，继续循环，直到队列为空，返回\(ans\)。

代码

class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.length();
        unordered_map<string, bool> isVisit; // 判断字符串str是否遍历过
        queue<string> q;
        q.push(s);
        string ans = s;
        while (!q.empty()) {
            string front = q.front();
            q.pop();
            if (front < ans) ans = front; // 取字典序最小的字符串
            string rotate = front.substr(n - b) + front.substr(0, n - b); // 旋转当前字符串
            if (!isVisit[rotate]) { // 新的字符串则加入，并置isVisit为true
                q.push(rotate);
                isVisit[rotate] = true;
            }
            for (int i = 1; i < n; i += 2) { // 累加当前字符串
                front[i] = '0' + (front[i] - '0' + a) % 10;
            }
            if (!isVisit[front]) { // 新的字符串则加入，并置isVisit为true
                q.push(front);
                isVisit[front] = true;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度，空间复杂度：取决于集合isVisit的大小，即遍历的字符串的数量。