如何使用动态规划将字符串拆分为单词？（Python，递归，备忘录）

Question

我正在尝试写一段动态规划的代码，目的是把一个字符串拆分成有效的单词（有效性是通过查字典来判断的）。

如果这个字符串不能拆分成有效的单词，我想返回一个空字符串''。

#

这是我代码的第一个版本：

dictionary = {'cat':1,'hat':1,'in':1}

def memoize(f):
    cache = {}
    def memoize_function(*args):
        if args[0] not in cache:
            cache[args[0]] = f(*args)  # compute and cache result
        return cache[args[0]]
        memoize_function.cache = cache  
    return memoize_function

@memoize
def splitintowords_version1(mystring, word_list):
    if len(mystring) < 1:
        return word_list
    else:
        for i in range(len(mystring)):
            current_word = mystring[:i+1]
            remaining_word = mystring[i+1:]
            if current_word in dictionary:
                word_list = word_list + current_word + ' ' 
                return splitintowords_version1(remaining_word, word_list)
            if i == len(mystring)-1 and current_word not in dictionary:
                word_list = ''
                return word_list

虽然严格来说，这段代码是能工作的，但我知道它没有正确使用动态规划，因为即使字符串变短了，完整的单词列表还是被传递了。例如，在调用splitintowords_version1('catinhat')后，splitintowords_version1.cache里面有一些无意义的内容：

{'':'cat in hat'}

#

然后我重写了程序：

@memoize                
def splitintowords_version2(mystring):
    if len(mystring) < 1:
        return ''
    else:
        for i in range(len(mystring)):
            current_word = mystring[:i+1]
            remaining_word = mystring[i+1:]
            if current_word in dictionary:
                return current_word + ' ' + splitintowords_version2(remaining_word)
            if i == len(mystring)-1 and current_word not in dictionary:
                return ''

这个版本正确地缓存了值，但对于splitintowords_version2('catinhata')却返回了错误的结果。它返回了'cat in hat '，而不是空字符串''。

我觉得我只差最后一步就能把代码写对。有人能帮我吗？

谢谢！

Answer 1

你描述的情况是因为你在 splitintowords_version2 这个函数里用了递归。

如果字符串的最后一个字符在字典里找不到，它就会返回 ''（空字符串）。但是，这个空字符串会被加到之前的结果上（current_word + ' ' + splitintowords_version2(remaining_word)）。所以在你的例子中，返回的 '' 就被简单地加到了已经分开的 "cat in hat" 上，变成了 "cat in hat "。你需要做的是检查递归的返回值是否为空，如果是的话就返回一个空字符串。不过，这还不够，因为 splitintowords_version2 对于一个空输入字符串也会返回 ''。你可以通过为空字符串返回其他值来轻松解决这个问题，或者在字符串无法被分割时返回其他值（在下面的例子中，我为空字符串返回 ' ' 而不是 ''，因此你可能需要在之后用 string.strip 去掉多余的空格）：

@memoize                
def splitintowords_version2(mystring):
    if len(mystring) < 1:
        return ' '
    else:
        for i in range(len(mystring)):
            current_word = mystring[:i+1]
            remaining_word = mystring[i+1:]
            if current_word in dictionary:
                remaining_split = splitintowords_version2(remaining_word)
                if len(remaining_split) > 0:
                    return current_word + ' ' + remaining_split
                else:
                    return '' # Last part was not in the dictionary.
            if i == len(mystring) - 1 and current_word not in dictionary:
                return ''

另一种方法是，如果字符串无法被分割，就返回 None，并且（如果需要的话）把这个 None 包装在另一个函数里，这样在最终结果中（而不是在中间调用时）把 None 转换回空字符串。要做到这一点，把 '' 替换为 None，并把检查 len(remaining_split) > 0 改成 remaining_split != None。