C++程序 查找给定数字字符串所需的最小循环旋转次数,避免给定字符串集合
给定一个数字字符串 target ,长度为 N ,以及一个数字字符串 blocked ,每个字符串长度为 N 。任务是通过避免任何字符串转换成只包含 0 的原始字符串,找到将原始字符串转换为 target 所需的最小循环旋转次数。如果不可能,输出-1。
注意: 单个旋转意味着通过 1 单位增加或减少特定索引处的值。由于旋转是循环的,因此可以将0转换为9或将9转换为0。
示例:
输入: target = “7531”,blocked = {“1543”,“7434”,“7300”,“7321”,“2427”}
输出: 12
解释: “0000” -> “9000” -> “8000” -> “7000” -> “7100” -> “7200” -> “7210” -> “7310” -> “7410” -> “7510” -> “7520” -> “7530” -> “7531”
输入: target = “4231”,blocked = {“1243”,“4444”,“1256”,“5321”,“2222”}
输出: 10
实现: 为了解决这个问题,我们使用以下BFS方法:
- 创建一个长度为 N ,只包含 0 的字符串 start 。将其推送到队列中。队列被创建用于存储下一个可能的有效组合,该组合可以通过增加或减少一个字符来处理。
- 创建一个无序集合 avoid ,并将所有阻止的字符串添加到其中。
- 如果 start 或 target 在 avoid 中,那么无法达到所需的目标。
- 从队列中弹出 start 并遍历 start 的所有字符。通过保持其余常量不变,增加和减少每个字符一个单位,并检查字符串是否存在于 avoid 中。如果新的组合不等于target,并且不存在于 avoid 中,则将其推送到队列中,并插入 avoid 中,以防止在未来重复相同的组合。
- 一旦整个 start 的长度被遍历,对下一级执行相同的步骤。也就是说,对从 start 中获得并当前存在于队列中的有效字符串,重复以上步骤。
- 重复以上步骤,直到达到目标或没有进一步的组合,队列已变为空。
- 在任何时候,如果形成的字符串等于target,则返回 count 的值,该值保持BFS遍历的级数计数。count的值是所需的最小循环旋转次数。
- 如果不能获得更多的状态,并且队列为空,则输出 “Not Possible”。
Output:
**时间复杂度:O(N 3 ) **
辅助空间:O(N)