241. Different Ways to Add Parentheses

题目

https://leetcode.com/problems/different-ways-to-add-parentheses/description/

想法

这个应该有多种解法吧
转化为构建二叉树？

反正图省事，先用DP做一下，基本上就是算出每两个元素间可能的结果…
这样的话，要开一个三维的数组，因为dp[i][j]位置要存的是一个数组
不考虑，而且好像也不是那么回事

如果递归地遍历地话，会不会超时

其实，运算符就是一个二叉树的非叶结点，其有多少种组合，就会有多少种运算方式
这只是抽象出来了，如何写呢？

不会…

答案

class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        ans = []
        for i, c in enumerate(input):
            if c in '+-*':
                for x in self.diffWaysToCompute(input[:i]):
                    for y in self.diffWaysToCompute(input[i + 1:]):
                        ans.append(eval(`x` + c + `y`))
        if not ans:
            return [int(input)]
        return ans

回顾

其实，简单的递归，就可以了，想的太多而没有动手去写

我想应该有更好的方法，但是，不想了…