我在这里发现的另一个stackerflow问题上看到了这个伪代码使用动态编程将字符串拆分为一个有效单词字符串。
这个问题是一个动态编程问题,看看输入字符串是否可以从字典中分割成单词。
第三行,表示将大小为[N+1]的数组b设置为所有假值?我很确定。但我真正不确定的是第五行。这是for循环还是什么?我觉得说"for I in range"的伪代码只有2个值。那句台词在说什么?
def try_to_split(doc):
N = len(doc)
b = [False] * (N + 1)
b[N] = True
for i in range(N - 1, -1, -1):
for word starting at position i:
if b[i + len(word)]:
b[i] = True
break
return b
这是一个令人困惑的语法,我敢肯定有一个错误。应该是:
for i in range(N - 1, 0, -1) //0, not -1
我认为这意味着
for i from (N - 1) downto 0 //-1 was the step, like i-- or i -= 1
这对算法来说是有意义的,因为它只是从字符串的末尾开始,并求解每个尾随的子字符串,直到它到达开头。如果b[0]在末尾是true
,则可以将输入字符串从字典中拆分为单词。for word starting at position i
只是检查字典中的所有单词,看看它们是否从那个位置开始。
如果想要重建解决方案,可以将b
更改为int数组,初始化为0s,并将if
更改为:
if b[i + len(word)] != 0
b[i] = i + len(word) //len(word) works too
break