• 42.2%

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

https://discuss.leetcode.com/topic/19906/c-4ms-recursive-dp-solution-with-brief-explanation

C++ 4ms Recursive & DP solution with brief explanation

Here is the basic recursive solution

substr(0, i) 0表示开始位置的index，i表示开index开始后的个数。

substr(i+1)，表示从i+1开始至字符串结尾。

There are many repeating subquestions in this recursive method, therefore, we could use dynamic programming to avoid this situation by saving the results for subquestions. Here is the DP solution.

https://discuss.leetcode.com/topic/19894/1-11-lines-python-9-lines-c

1-11 lines Python, 9 lines C++

Just doing it…

Solution 1 … 48 ms

Solution 2 … 168 ms

One-liner inspired by Soba.

Solution 3 … 64 ms

Faster version of solution 2.

Solution 4 … 188 ms

A code golf version of solution 2.

C++ … 8 ms

C++ version of solution 3.

https://discuss.leetcode.com/topic/22179/python-easy-to-understand-solution-divide-and-conquer

Python easy to understand solution (divide and conquer).

https://discuss.leetcode.com/topic/27532/14-line-c-solution

14-line c++ solution

https://discuss.leetcode.com/topic/20516/c-solution-using-dp-easy-understanding

C++ solution, using dp, easy understanding

https://discuss.leetcode.com/topic/20814/python-solution-use-dp

Python solution use dp

First I extracted the numbers and operators in the expression. Assume there are d numbers and d-1 operators.

dp[ i ][ j ] is all possible results of expression contains num[ i : j+1 ].

So the first loop we calculate expressions only have 2 numbers, then 3 numbers, then 4 numbers….

Let’s say we want to get the result of expression contains L numbers started from num[ j ] , we divide it by two half, the first one contains k numbers, and the second half contains L-k numbers. The result of the first half is dp[ j ][ j+k-1 ] and the second half is dp[j+k-1][ j+l-1]. dp[ i ][ j ] contains all combinations of x from dp[ j ][ j+k-1 ] and y from dp[ j+k-1: j+l-1 ], and k is from 1 to l-1.

10ms, 15.08%, October 15, 2016

https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms