求问一个leetcode上的时间复杂度问题

Leetcode上的Word Break 2 ：http://oj.leetcode.com/problems/word-break-ii/

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

这个问题我用两种方法解：

1.dp保存在0~k位置子串被分割的解集，k+1位置的就可以通过遍历0~k位置解集来获得。最后返回dp[n]

2.二维dp保存[i,j]是否可以通过i~j是解集中的一个单独子串，0~i-1是一个可能解集的方法分割，然后dfs遍历生成结果。

我表达的可能不太好，我把代码贴在最后面。方法2能AC，方法1超时，但是其实我理解的是dfs重复计算了一部分中间结果，比如2个不同的最终解集都包含了位置0~4（举例）子串的解集，那不就是重复计算了两边吗？而方法1只要用dp[4]就可以了。

总的来说我觉得方法1的时间复杂度是O(n^3)，而dfs方法似乎是指数级别的（虽然用提前计算的dp剪枝掉一些，但是似乎没有影响渐进的时间复杂度）

用的是python，发代码的功能似乎不支持缩进所以就直接PO上来了。

方法1的代码：

class Solution:

    # @param s, a string

    # @param dict, a set of string

    # @return a list of strings

    def wordBreak(self, s, dict):

        dp=[]

        f=[]

        for i in range(len(s)):

            ft=[]

            for j in range(i,len(s)):

                st=s[i:j+1]

                if st in dict:

                    ft.append(True)

                else:

                    ft.append(False)

            f.append(ft)

        for i in range(len(s)):

            arri=[]

            for j in range(i):

                s2=s[j+1:i+1]

                if f[j+1][i-j-1]:

                    tmp=""

                    dpj=dp[j]

                    for t in dpj:

                        tmp=t

                        tmp+=" "+s2

                        if len(tmp)>0:

                            arri.append(tmp)

            if f[0]:

                arri.append(s[:i+1])

            dp.append(arri)

        return dp[len(s)-1]

方法2的代码

class Solution:

    # @param s, a string

    # @param dict, a set of string

    # @return a list of strings

    def wordBreak(self, s, dict):

        dp=[]

        f=[]

        self.fill(f,len(s),False)

        f.insert(0,True)

        for i in range(len(s)):

            l=[]

            self.fill(l, len(s), False)

            dp.append(l)

        for i in range(len(s)):

            for j in range(i,-1,-1):

                if f[j] and s[j:i+1] in dict:

                    f[i+1]=True

                    dp[j]=True

        ans=[]

        path=[]

        self.dfs(ans, path, len(s)-1, dp,s)

        return ans

    def dfs(self,ans,path,cur,dp,s):

        if cur==-1:

            w=""

            for i in range(len(path)):

                if i>0:

                    w=" "+w

                w=path+w

            ans.append(w)

            return

        for i in range(cur+1):

            if dp[cur]:

                path.append(s[i:cur+1])

                self.dfs(ans, path, i-1, dp, s)

                path.pop()

    def fill(self,l,n,c):

        for i in range(n):

            l.append(c)

[i][i]

[/i][/i]