找到将一个二进制字符串更改为另一个字符串所需的最

Question

给定两个只包含0or的字符串str1和str2 1,有一些步骤可以将str1更改为str2,

step1:找到长度为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中,不可能更改length3子串使它与众不同 所以输出为-1.

例3

str1 ="10101010",str2 ="00101011",输出为7

我无法弄清楚示例3,因为有两种可能性.任何人都可以提供一些如何解决这个问题的提示吗？这个问题是什么类型的？是动态编程吗？

Answer 1

这实际上是一个动态规划问题。为了解决这个问题，我们将尝试所有可能的排列，但一路记住结果。似乎有太多的选项 - 有2^30长度为 30 的不同二进制字符串，但请记住，恢复字符串不会改变我们拥有的 0 和 1 的数量，因此上限实际上是30 choose 15 = 155117520当我们有由 15 个 0 和 1 组成的字符串。大约 1.5 亿个可能的结果还算不错。

因此，从我们的start字符串开始，我们将从迄今为止导出的每个字符串中导出所有可能的字符串，直到生成end字符串。我们还要追踪前人，重建一代。这是我的代码：

start = '10101010'
end = '00101011'

dp = [{} for _ in range(31)]
dp[1][start] = '' # Originally only start string is reachable

for i in range(2, len(start) + 1):
  for s in dp[i - 1].keys():
    # Try all possible reversals for each string in dp[i - 1]
    for j in range(len(start) - i + 1):
      newstr = s
      newstr = newstr[:j] + newstr[j:j+i][::-1] + newstr[j+i:]
      dp[i][newstr] = s
  if end in dp[i]:
    ans = []
    cur = end
    for j in range(i, 0, -1):
      ans.append(cur)
      cur = dp[j][cur]
    print(ans[::-1])
    exit(0)

print('Impossible!')

对于第三个示例，这为我们提供了序列['10101010', '10101001', '10101100', '10100011', '00101011']- 从 str1 到 str2。如果您检查字符串之间的差异，您将看到进行了哪些转换。因此，这种转换可以通过 4 个步骤完成，而不是像您建议的那样 7 个步骤。

最后，这对于 python 中的 30 来说会有点慢，但是如果你将其重写为 C++，则最多需要几秒钟。