用Python编写的查找修正方程所需纠正数字数量的程序

假设我们有一个字符串s，它代表形如x+y=z的方程。我们必须找到需要添加到s中的最小数字数量，以使等式成立。

因此，如果输入为s=’2+6=7’，则输出将为2。

我们可以将方程转换为“21+6=27”通过插入“1”和“2”。因此，所需的总纠正数量为2。

要解决这个问题，我们将遵循以下步骤：

将s根据“+”字符分成若干部分，将左边的部分放入A中，将右边的部分放入rest中
将rest根据“=”字符分成若干部分，将左边的部分放入B中，将右边的部分放入C中
返回dp(A的大小-1，B的大小-1，C的大小-1，0)
定义一个函数dp()。这将需要i，j，k，carry
如果i <= -1且j <= -1且k <= -1，则
- 如果进位与0相同，则返回0，否则返回1
如果i >= 0，则last1 :=（A[i]），否则为0
如果j >= 0，则last2 :=（B[j]），否则为0
如果k >= 0，则last3 :=（C[k]），否则为0
如果i >= 0，则prefix1 :=（从索引0到i + 1的A）；否则为0
如果j >= 0，则prefix2 :=（从索引0到j + 1的B）；否则为0
如果k >= 0，则prefix3 :=（从索引0到k + 1的C）；否则为0
如果i <= -1且j <= -1，则
- rhs :=prefix 3 – 进位
- 如果rhs <= 0，则
  - 返回|rhs|
- 如果i与-1相同或j与-1相同，则
  - 返回rhs字符串的大小
- 否则，
  - 返回False
- 如果k <= -1，则
  - 返回prefix1 + prefix2 + carry的字符串大小
- ans := infinity
- carry2，lhs :=将（carry + last1 + last2）除以10的商和余数返回
- 如果lhs与last3相同，则
  - ans := dp（i-1，j-1，k-1，carry2）
- req := last3 – carry – last2
- extra_zeros :=最大值为0，-1-i
- 如果req <0，则carry2 := 1，否则为0
- ans := ans和1 + extra_zeros + dp（maximum of-1，i，j-1，k-1，carry2）的最小值
- req := last3 – carry – last1
- extra_zeros := maximum of 0，-1-j
- 如果req <0，则carry2 := 1，否则为0
- ans = ans和dp（i-1，max（-1，j），k-1，carry2）的1 + extra_zeros的最小值
- carry2，lhs :=将（last1 + last2 + carry）除以10的商和余数返回
- ans := ans和1 + dp（i-1，j-1，k，carry2）的最小值
- 返回ans
从主方法返回dp（A的大小-1，B的大小-1，C的大小-1，0）

例子

看看以下实现以更好地理解-

class Solution:
   def solve(self, s):
      A, rest = s.split("+")
      B, C = rest.split("=")
      def dp(i, j, k, carry):
         if i <= -1 and j <= -1 and k <= -1:
            return 0 if carry == 0 else 1
         last1 = int(A[i]) if i >= 0 else 0
         last2 = int(B[j]) if j >= 0 else 0
         last3 = int(C[k]) if k >= 0 else 0
         prefix1 = int(A[: i + 1]) if i >= 0 else 0
         prefix2 = int(B[: j + 1]) if j >= 0 else 0
         prefix3 = int(C[: k + 1]) if k >= 0 else 0
         if i <= -1 and j <= -1:
            rhs = prefix3 - carry
            if rhs <= 0:
               return abs(rhs)
            if i == -1 or j == -1:
               return len(str(rhs))
            else:
               assert False
         if k <= -1:
            return len(str(prefix1 + prefix2 + carry))
         ans = float("inf")
         carry2, lhs = divmod(carry + last1 + last2, 10)
         if lhs == last3:
            ans = dp(i - 1, j - 1, k - 1, carry2)
         req = last3 - carry - last2
         extra_zeros = max(0, -1 - i)
         carry2 = 1 if req < 0 else 0
         ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
         req = last3 - carry - last1
         extra_zeros = max(0, -1 - j)
         carry2 = 1 if req < 0 else 0
         ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
         carry2, lhs = divmod(last1 + last2 + carry, 10)
         ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
         return ans
      return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)

ob = Solution()
print (ob.solve('2+6=7'))