首页 文章

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

提问于
浏览
5

给定两个字符串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 回答

  • 0

    这实际上是一个动态编程问题 . 为了解决这个问题,我们将尝试所有可能的排列,但是在整个过程中记住结果 . 似乎有太多选项 - 有 2^30 长度为30的不同二进制字符串,但请记住,恢复字符串不会改变零和我们拥有的数量,所以上限实际上是 30 choose 15 = 155117520 我们有一串15个零和一个 . 大约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,它将是几秒钟的顶部 .

相关问题