遇到一个恢复字符串问题，求解答。
给出两个仅包含“+”、“-”两种字符且长度相同字符串 s1、 s2，你需要通过填充数字将这两个字符串恢复成一个合法的表达式。并且只能填入正整数，恢复后的表达式的值必须非负。例如对于字符串“+-”，你可以将其变成“1+1-2”，但是不可以变成“1+1-3”，也不可以变成“1+0-1”。定义你的消耗为你填充的所有正整数的和。比如“1+1-2”的消耗为1+1 +2= 4。你需要将这两个字符串都恢复成合法表达式，并且尽量的使它们的差值最小，于此同时你还需要使你的消耗最小。相信你通过思考已经发现最小差值总是 0，因此你只需要求出差值为 0 时的最小消耗即可。字符串长度都小于 100000。输入两个字符串s1和s2。输出一个数字，表示最小消耗。
写回答
-
首先可以确定最小值一定为 0。分两种情况讨论: 1. 两个字符串都没有负号的时候，最优解的所有位置都填 1。最小消耗为 2*（n+1）。 2. 表达式中仅需要有一个负号，表达式的值就可以为任何值。此时两个表达式可以相互调整，因此最小差也是 0。 表达式中除了第一位以外每位数字填 1 可以得到最小消耗，因为值加在哪一位都 是等效的。不妨假设都加在第一位。计算出 s1,s2 的正负号数量的差，分别为 x 和 y。假设第一位分别为 pa，pb，我们只需要使（pa+x==pb+y）即可。假设最终表达式的值为 final，则 final=max(max(x, y) +1, 0)，则pa=final-x，pb=final-y。 因此：输入：“++-” “--+” 输出：10
2021-12-23 18:31:41赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
