在Python中查找应用操作后字典序最小的字符串的程序
假设我们有一个仅由数字组成的字符串s,还有两个值a和b。我们可以任意次数地任意顺序地在s上应用以下两个操作之一−
- 将’a’添加到s的所有奇数位置的项目上(0索引)。如果数字是9,则添加后会被循环回0。
-
将’s’向右旋转b个位置。
因此,我们必须通过对s应用上述操作并任意次数,找到可以获得的字典序最小的字符串。
因此,如果输入如下:s =“5323”,a = 9,b = 2,则输出为“2050”,因为如果我们按照以下方式操作
- 旋转:”5323″
- 添加:”5222″
- 添加:”5121″
- 旋转:”2151″
- 添加:”2050″
要解决这个问题,我们将按照以下步骤进行 −
- seen:=一个新的集合
- deq:=一个新的队列,其中包含一个元素’s’
- while deq不为空,执行以下操作
- curr:=删除deq的第一个元素
- 将curr插入seen集合
- ad:=对curr执行给定的添加操作
- 如果ad不在seen中,则
- 将ad插入到deq的末尾
- 将ad插入seen集合中
- ro:=对curr执行旋转操作
- 如果ro不在seen中,则
- 将ro插入到deq的末尾
- 将ro插入seen集合中
- 返回seen的最小值
示例
让我们看一下以下实现,以获得更好的理解−