【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“111.恢复字符串”的解法探究。先来看一下题目内容：
题目详情
等级：中等
知识点：贪心
查看题目：恢复字符串
给出两个仅包含“+”、“-”两种字符且长度相同字符串s1、 s2，你需要通过填充数字将这两个字符串恢复成一个合法的表达式。并且只能填入正整数，恢复后的表达式的值必须非负。
例如对于字符串“+-”，你可以将其变成“1+1-2”，但是不可以变成“1+1-3”，也不可以变成“1+0-1”。定义你的消耗为你填充的所有正整数的和。比如“1+1-2”的消耗为 1 + 1 + 2 = 4。你需要将这两个字符串都恢复成合法表达式，并且尽量的使它们的差值最小，于此同时你还需要使你的消耗最小。
相信你通过思考已经发现最小差值总是0，因此你只需要求出差值为0时的最小消耗即可。字符串长度都小于100000。
输入两个字符串s1和s2。
输出一个数字，表示最小消耗。
示例1
输入：
“++-”
“--+”
输出：
10
注意
样例最优解为“1+1+1-1”，“3-1-1+1”。
解题方法：
首先可以确定最小值一定为0。分两种情况讨论。
- 两个字符串都没有负号的时候，最优解的所有位置都填1。最小消耗为 2*（n+1）。
- 表达式中仅需要有一个负号，表达式的值就可以为任何值。此时两个表达式可以相互调整，因此最小差也是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。
看完之后是不是有了答题思路了呢，快来练练手吧：111.恢复字符串
在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！