讨论下lc最新的那道hard题吧

http://www.mitbbs.com//article_t/JobHunting/33056247.html

发信人: jingi08 (骑驴中), 信区: JobHunting
标  题: 讨论下lc最新的那道hard题吧
发信站: BBS 未名空间站 (Sat Sep 19 01:33:41 2015, 美东)

题目如下：
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.

给的几个例子：
"123", 6 -> ["1+2+3", "1*2*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 -> []


下面是我的java code，有个test case一直超时，求大牛指点优化。我的思路很简单，
先生成所有可能的计算式，然后对每个计算式求值与target比较。

public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<String>();
        if(num == null || num.length() == 0) return result;
        List<String> expressions = new ArrayList<String>();
        generate(num, expressions, 0, "");
        for(String str : expressions)
            if(evaluate(str) == target) result.add(str);
        return result;
    }
   
    private void generate(String num, List<String> result, int pos, String
currResult) {
        if(pos == num.length()) {
            result.add(currResult);
            return;
        }
        String currStr = currResult + num.substring(pos, pos+1);
        if(pos == num.length() - 1) {
            generate(num, result, pos+1, currStr);
        } else {
            // apply '+'
            generate(num, result, pos+1, currStr+"+");
            // apply '-'
            generate(num, result, pos+1, currStr+"-");
            // apply '*'
            generate(num, result, pos+1, currStr+"*");
            // no operator, combine digits
            generate(num, result, pos+1, currStr);
        }
    }
   
    private long evaluate(String str) {
        LinkedList<Long> operand = new LinkedList<>();
        LinkedList<Character> operator = new LinkedList<>();
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '+' || str.charAt(i) == '-' || str.charAt(i)
== '*') {
                operator.offer(str.charAt(i));
                continue;
            }
            long val = 0;
            while(i < str.length() && str.charAt(i) >= '0' && str.charAt(i)
<= '9') {
                val = val * 10 + str.charAt(i) - '0';
                i++;
            }
            i--;
            operand.offer(val);
            if(operator.size() > 0 && operator.peekLast() == '*') {
                operator.pollLast();
                operand.offer(operand.pollLast() * operand.pollLast());
            }
        }
        // evaluate the remaining part
        while(!operator.isEmpty()) {
            char optor = operator.poll();
            long operand1 = operand.poll();
            long operand2 = operand.poll();
            if(optor == '+') {
                operand.offerFirst(operand1 + operand2);
            } else {
                operand.offerFirst(operand1 - operand2);
            }
        }
        return operand.poll();
    }
--