C++ 通过避免一组给定的字符串来最小化循环旋转所需次数以得到给定的数值字符串
在这个问题中,我们将找到从包含N个0的字符串到目标字符串所需的旋转次数。同时,我们将在进行旋转时跳过数组中给定的字符串。
我们可以使用BFS算法来找到获得目标字符串所需的最小旋转次数。
问题陈述
我们已经给出了一个包含N个数字符号的目标字符串。同时,我们还提供了一个包含尺寸为N的M个字符串的strs[]数组,其中包含数字字符。我们需要通过多次执行给定的操作,从一个包含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 - 如果 skip 集合包含 target_str 或目标字符串,则返回 -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’ 集合中,则将其推入队列中。同时,将 str 插入跳过集合,因为我们已经访问过它。所以,下次我们需要跳过它。
-
步骤 5.2.6 - 将 str[p] 初始化为 c – 1。如果 str[p] 变小于 ‘0’,则将其更新为 ‘9’。
-
步骤 5.2.7 - 如果更新后的 str 等于目标字符串,则返回旋转次数。否则,如果队列中不存在 str,则将其插入队列中。
-
步骤 5.2.8 - 将 str 插入 ‘skip’ 集合中。
-
步骤 5.2.9 - 使用原始字符 c 更新 str[p]。
-
步骤 6 - 当无法获取目标字符串时,返回 -1。
例子
#include <bits/stdc++.h>
using namespace std;
int minRotations(string target, vector<string> &strs, int N) {
string target_str = "";
// Create a string containing N '0'
for (int p = 0; p < N; p++) {
target_str += '0';
}
unordered_set<string> skip;
// Insert given string in the set
for (int p = 0; p < strs.size(); p++)
skip.insert(strs[p]);
// Base case
if (skip.find(target_str) != skip.end())
return -1;
if (skip.find(target) != skip.end())
return -1;
queue<string> que;
que.push(target_str);
// To store a number of rotations
int rotations = 0;
// BFS algorithm
while (!que.empty()) {
rotations++;
int len = que.size();
for (int q = 0; q < len; q++) {
string str = que.front();
que.pop();
// Traverse the string
for (int p = 0; p < N; p++) {
char c = str[p];
// INcrement the character
str[p]++;
// Rotate the character
if (str[p] > '9')
str[p] = '0';
// If we got the targeted string
if (str == target)
return rotations;
// When we don't need to skip the string
if (skip.find(str) == skip.end())
que.push(str);
// Add in the set to skip as we already visited
skip.insert(str);
// Do the same thing after decreasing the current character by 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 << "The minimum rotations required to get the target string is - " << minRotations(target, strs, N) << endl;
return 0;
}
输出结果
The minimum rotations required to get the target string is - 12
-
时间复杂性 − O(NNN)
-
空间复杂性 − O(N)
结论
我们使用set来跟踪已访问的字符串,并使用队列存储更新的字符串。在每次旋转中,我们更新从前一个迭代得到的字符串。当我们第一次找到目标字符串时,我们返回旋转次数,因为BFS算法总是提供最小路径值。