Leetcode: Word Break II @Python

class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a list of strings
    def wordBreak(self, s, dict):
        n=len(s)
        A=[[] for i in range(n)]
        i=n-1
        while i>=0:
            if s[i:n] in dict:
                A[i].append(n)
            for j in range(i+1,n):
                if A[j] and s[i:j] in dict:
                    A[i]+=[j]
            i-=1
        path=[[0]]
        rst=[]
        while path:
            new_path=[]
            for i in path:
                if i[-1]==n:
                    temp=[s[i[k]:i[k+1]] for k in range(len(i)-1)]
                    rst.append(' '.join(temp))
                else:
                    for node in A[i[-1]]:
                        new_path.append(i+[node])
            path=new_path
        return rst