通过避开一组给定的字符串，求出获取给定数字字符串的最小循环旋转次数
在本题中，我们将求出从包含 N 个 0 的字符串到目标字符串所需的旋转次数。此外，在旋转过程中，我们将跳过数组中指定的字符串。
我们可以使用广度优先搜索 (BFS) 算法来求出获取目标字符串所需的最小旋转次数。
问题描述
我们给定了一个包含 N 个数字字符的目标字符串。此外，我们还给出了 strs[] 数组，其中包含 M 个大小为 N 的字符串，每个字符串都包含数字字符。我们需要通过多次执行给定的操作，从包含 N 个 0 的字符串到目标字符串。在单次操作中，我们可以旋转字符串的任意字符，但我们需要确保在任何旋转操作中，都不会得到 strs[] 包含的字符串。我们需要找到从初始字符串获取目标字符串所需的最小旋转次数。
注意 − 我们可以将 9 旋转为 0，也可以将 0 旋转为 9。
示例
输入
N = 4; target = "7531"; strs = {"1543", "7434", "7300", "7321", "2427"};
输出
12
说明
我们需要从 0000 字符串开始。之后，我们可以进行以下旋转，并在旋转字符串时跳过数组包含的字符串。
0000 → 9000 → 8000 → 7000 → 7900 → 7800 → 7700 → 7600 → 7500 → 7510 → 7520 → 7530 → 7531
这里，我们跳过了 7300 这个字符串。另一种解决方案如下所示。
0000 → 9000 → 8000 → 7000 → 7100 → 7200 → 7210 → 7310 → 7410 → 7510 → 7520 → 7530 → 7531
输入
N = 4; target = "7531"; strs = {"7513", "7434", "7300", "7321", "2427"};
输出
-1
说明
目标字符串存在于数组中，我们需要跳过数组包含的所有字符串。因此，无论如何都无法获得目标字符串。
方法
在此方法中，我们将正向和反向旋转给定字符串的每个字符。之后，我们将更新后的字符串插入队列。在下一次迭代中，我们将从上一次迭代中获取所有字符串，更新它们，然后将它们插入队列。
在更新字符串时，我们将确保跳过 strs[] 数组中的字符串。当我们获得目标字符串时，我们将返回所需的旋转总数。
算法
步骤 1 − 用 N 个 0 初始化 target_str。我们将更新 target_str 字符串以获取目标字符串。
步骤 2 − 另外，定义"skip"集合来存储我们需要跳过的字符串。因此，将所有 strs[] 类型的字符串插入到该集合中。
步骤 3 − 如果跳过集合包含 target_str 或 target 字符串，则返回 -1。
步骤 4 − 定义字符串队列，并将 target_str 字符串插入队列。另外，定义 'rotations' 来存储旋转次数。
步骤 5 - 遍历队列。
步骤 5.1 - 增加旋转次数并获取队列长度。
步骤 5.2 - 使用 for 循环遍历队列的所有元素。
步骤 5.2.1 - 从队列中获取最前面的元素，并将其存储在 'str' 字符串变量中。
步骤 5.2.2 - 遍历 'str' 字符串的每个字符。
步骤 5.2.3 - 将 str[p] 存储到字符 'c' 中，并将 str[p] 加 1。如果str[p] 大于 '9'，将其更新为 '0'。
步骤 5.2.4 − 如果当前字符串是目标字符串，则返回旋转值。
步骤 5.2.5 − 如果 str 不存在于 skip 集合中，则将其推送到队列中。此外，由于我们已经访问过 skip 集合，因此将 str 插入 skip 集合。因此，下次我们需要跳过它。
步骤 5.2.6 − 用 c − 1 初始化 str[p]。如果 str[p] 小于 '0'，则将其更新为 '9'。
步骤 5.2.7 − 如果更新后的 str 等于目标字符串，则返回旋转值。否则，如果集合中不存在 str，则将其插入队列。
步骤 5.2.8 - 将 str 插入"skip"集合。
步骤 5.2.9 - 将 str[p] 更新为 c，即原始字符。
步骤 6 - 当无法获取目标字符串时，返回 -1。
示例
#include <bits/stdc++.h>
using namespace std;
int minRotations(string target, vector<string> &strs, int N) {
string target_str = "";
// 创建一个包含 N 个"0"的字符串
for (int p = 0; p < N; p++) {
target_str += '0';
}
unordered_set<string> skip;
// 将给定的字符串插入到集合中
for (int p = 0; p < strs.size(); p++)
skip.insert(strs[p]);
// 基本情况
if (skip.find(target_str) != skip.end())
return -1;
if (skip.find(target) != skip.end())
return -1;
queue<string> que;
que.push(target_str);
// 存储旋转次数
int rotations = 0;
// 广度优先搜索 (BFS) 算法
while (!que.empty()) {
rotations++;
int len = que.size();
for (int q = 0; q < len; q++) {
string str = que.front();
que.pop();
// 遍历字符串
for (int p = 0; p < N; p++) {
char c = str[p];
// 字符递增
str[p]++;
// 字符旋转
if (str[p] > '9')
str[p] = '0';
// 如果我们找到了目标字符串
if (str == target)
return rotations;
// 当我们不需要跳过字符串时
if (skip.find(str) == skip.end())
que.push(str);
// 添加到要跳过的集合中，因为我们已经访问过了
skip.insert(str);
// 将当前字符减 1，然后执行相同的操作
str[p] = c - 1;
if (str[p] < '0')
str[p] = '9';
if (str == target)
return rotations;
if (skip.find(str) == skip.end())
que.push(str);
skip.insert(str);
str[p] = c;
}
}
}
return -1;
}
int main() {
int N = 4;
string target = "7531";
vector<string> strs = {"1543", "7434", "7300", "7321", "2427"};
cout << "获取目标字符串所需的最小旋转次数是 - " << minRotations(target, strs, N) << endl;
return 0;
}
输出
获取目标字符串所需的最小旋转次数是 - 12
时间复杂度 − O(N*N*N)
空间复杂度 − O(N)
结论
我们使用集合来跟踪访问过的字符串，并使用队列来存储更新后的字符串。在每次旋转中，我们都会更新上一次迭代得到的字符串。每当我们第一次找到目标字符串时，我们都会返回旋转次数，因为广度优先搜索 (BFS) 算法总是提供最小路径值。
