给定两个字符串str1和str2只包含0或1,有一些步骤将str1更改为str2,步骤1:找到长度为2的str1子串并反转子串,str1变为str1'(str1'!= str1 )step2:找到长度为3的str1'的子串,并反转子串,并且str1'变为str1''(str1''!= str1'),以下步骤类似 . 字符串长度在[2,30]范围内要求:每个步骤必须执行一次,我们不能跳过前面的步骤并执行下一步 . 如果可以将str1更改为str2,则输出所需的最小步数,否则输出-1
示例1
str1 =“1010”,str2 =“0011”,所需的最小步长为2,在范围[2,3],“1010” - >“1001”中选择子串,然后选择范围[0, 2],“1001” - >“0011”
示例2
str1 =“1001”,str2 =“0110”,不可能将str1更改为str2,因为在步骤1中,str1可以更改为“0101”或“1010”,但在步骤3中,不可能更改长度3 substring使它与众不同 . 所以输出为-1 .
示例3
str1 =“10101010”,str2 =“00101011”,输出为7
我无法弄清楚示例3,因为有两种可能性 . 任何人都可以提供一些如何解决这个问题的提示吗?这个问题是什么类型的?是动态编程吗?
1 回答
这实际上是一个动态编程问题 . 为了解决这个问题,我们将尝试所有可能的排列,但是在整个过程中记住结果 . 似乎有太多选项 - 有
2^30
长度为30的不同二进制字符串,但请记住,恢复字符串不会改变零和我们拥有的数量,所以上限实际上是30 choose 15 = 155117520
我们有一串15个零和一个 . 大约1.5亿可能的结果也不算太糟糕 .所以从我们的
start
字符串开始,我们将从我们到目前为止导出的每个字符串派生所有可能的字符串,直到我们生成end
字符串 . 我们还将跟踪前辈重建发电 . 这是我的代码:对于你的第三个例子,这给了我们序列
['10101010', '10101001', '10101100', '10100011', '00101011']
- 从你的str1到str2 . 如果检查字符串之间的差异,您将看到进行了哪些转换 . 所以这个转换可以按照你建议的4个步骤而不是7个步骤完成 .最后,对于python中的30,这将有点慢,但如果你将它重写为C,它将是几秒钟的顶部 .