python – 使用动态编程进行分词

所以首先我对Python很陌生,所以如果我做了一件糟糕的事情,我会抱歉这个帖子.我被分配了这个问题：

我们想为下面的问题设计一个动态编程解决方案：有一个字符串可能是一系列单词,删除了所有空格,我们想找到一种方法,如果有的话,在其中插入空格单独的有效英语单词.例如,他们的故事可能来自“你的发泄”,“青年事件”或“他们出去发泄”.如果输入是theeaglehaslande,则没有这样的方法.您的任务是以两种不同的方式实现动态编程解决方案：

>迭代自下而上版本
>递归记忆版

假设单词的原始序列没有其他标点符号(例如句点),没有大写字母,也没有专有名称 – 所有单词都将在提供给您的字典文件中提供.

所以我有两个主要问题：

>我知道这可以而且应该在O(N ^ 2)中完成,我不认为我的是
>查找表不会添加所有单词,这样可以减少时间复杂度

我想要的是什么：

>任何类型的输入(更好的方法,你在代码中看到错误的东西,我如何使查找表工作,如何使用布尔表来构建一系列有效的单词)
>关于如何处理递归版本的一些想法,虽然我觉得一旦我能够解决迭代解决方案,我将能够设计递归版本.

一如既往地感谢任何人给予的任何时间和努力,我们总是感激不尽.

这是我的尝试：

#dictionary function returns True if word is found in dictionary false otherwise
def dictW(s):
    diction = open("diction10k.txt",'r') 
    for x in diction:
        x = x.strip("n r")
        if s == x:
            return True
    return False

def iterativeSplit(s):
    n = len(s)
    i = j = k = 0
    A = [-1] * n
    word = [""] * n
    booly = False
    for i in range(0,n):
        for j in range(0,i+1):
            prefix = s[j:i+1]
            for k in range(0,n):

                if word[k] == prefix:
                    #booly = True
                    A[k] = 1
                    #print "Array below at index k %d and word = %s"%(k,word[k])
                    #print A
            # print prefix,A[i]
            if(((A[i] == -1) or (A[i] == 0))):
                if (dictW(prefix)):
                    A[i] = 1
                    word[i] = prefix
                    #print word[i],i
                else:
                    A[i] = 0
    for i in range(0,n):
        print A[i]