string - 找到将一个二进制字符串更改为另一个所需的最少步骤

Question

Given two string str1 and str2 which contain only 0 or 1, thereare some steps to change str1 to str2,

step1: find a substring of str1 of length 2 and reverse the substring, and str1 becomes str1' (str1' != str1)

step2: find a substring of str1' of length 3, and reverse the substring, and str1' becomes str1'' (str1'' != str1')

the following steps are similar.

the string length is in the range [2, 30]

Requirement: each step must be performed once and we can not skipprevious steps and perform the next step.

If it is possible to change str1 to str2, output the minimum steps required, otherwise, output -1

例子1

str1 = "1010", str2 = "0011", the minimum step required is 2

first, choose substring in range [2, 3], "1010" --> "1001",

then choose substring in the range [0, 2], "1001" --> "0011"

例子2

str1 = "1001", str2 = "0110", it is impossible to change str1 to str2,because in step1, str1 can be changed to "0101" or "1010", but in step3, it is impossible to change a length3 substring to make it different. So the output is -1.

示例 3

str1 = "10101010", str2 = "00101011"， output is 7

我想不通示例 3，因为有两种可能性。任何人都可以就如何解决这个问题给出一些提示吗？这是什么类型的问题？是动态规划吗？

Answer 1

这实际上是一个动态规划问题。为了解决这个问题，我们将尝试所有可能的排列，但一路上记住结果。似乎有太多选择 - 有 2^30 长度为 30 的不同二进制字符串，但请记住，恢复字符串不会改变我们拥有的零和一的数量，所以上限实际上是 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 个步骤。

最后，对于 30 位的 python 来说，这会有点慢，但是如果你将它重写成 C++，它会最多几秒钟。