Expression Add Operators
題意:
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"]
"123", 15 -> ["12+3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
解題思路:
此為Combination Sum 的變形,我們可以使用dfs來幫助我們解這道題,加與減很好處理,這邊需要特別處理的是乘的部份
網友 ethannnli 提供了以下詳細的思路:
乘號之前是加號或減號,例如2+3*4,我們在2那裡算出來的結果,到3的時候會加上3,計算結果變為5。在到4的時候,因為4之前我們選擇的是乘號,這裡3就應該和4相乘,而不是和2相加,所以在計算結果時,要將5先減去剛才加的3得到2,然後再加上3乘以4,得到2+12=14,這樣14就是到4為止時的計算結果。
另外一種情況是乘號之前也是乘號,如果2+345,這裡我們到4為止計算的結果是14了,然後我們到5的時候又是乘號,這時候我們要把剛才加的34給去掉,然後再加上345,也就是14-34+345=62。這樣5的計算結果就是62。
因為要解決上述幾種情況,我們需要這麼幾個變量,一個是記錄上次的計算結果currRes,一個是記錄上次被加或者被減的數prevNum,一個是當前準備處理的數currNum。當下一輪搜索是加減法時,prevNum就是簡單換成currNum,當下一輪搜索是乘法時,prevNum是prevNum乘以currNum。
注意
第一次搜索不添加運算符,只添加數字,就不會出現+1+2這種表達式了。 我們截出的數字不能包含0001這種前面有0的數字,但是一個0是可以的。這裡一旦截出的數字前導為0,就可以return了,因為說明前面就截的不對,從這之後都是開始為0的,後面也不可能了。
程式碼如下:
public class Solution {
List<String> res;
public List<String> addOperators(String num, int target) {
res = new ArrayList<String>();
if (num == null || num.length() == 0) {
return res;
}
helper(num, target, new String(), 0, 0);
return res;
}
private void helper(String num, int target, String tempRes, long curRes, long prevNum) {
if (curRes == target && num.length() == 0) {
res.add(new String(tempRes));
return;
}
for (int i = 1; i <= num.length(); i++) {
String cur = num.substring(0, i);
// 捨棄"00"之類的值
if (cur.length() > 1 && cur.charAt(0) == '0') {
return;
}
long curNum = Long.parseLong(cur);
String next = num.substring(i); //把剛取出來的那個丟掉,因下一輪不能再取
// 如果不是第一個數字的話,後面才要附上加減乘
if (tempRes.length() != 0) {
helper(next, target, tempRes + "+" + curNum, curRes + curNum, curNum);
helper(next, target, tempRes + "-" + curNum, curRes - curNum, -curNum);
helper(next, target, tempRes + "*" + curNum, (curRes - prevNum) + prevNum * curNum, prevNum * curNum);
} else {
helper(next, target, cur, curNum, curNum);
}
}
}
}