将一串字符分解为有效字

我正在阅读有关动态规划的一个问题。问题如下：将一串字符分解为有效字

将长度为n的字符串拆分为有效的单词序列。假设有一个数据结构告诉你一个字符串在常量时间内是否是一个有效的单词。

我解决了它我的一些方式，但后来我读了解决方案是以下几点：

创建一个表T [N]它说，T [i]为真，如果子 [0 ... i]可以分解为一系列有效的单词。当且仅当存在AJ，0 < = j的< = K-1，其中T [j]为TRUE，并且S（J，K）是一个有效的字

这是经典的T [i]为真为DP制定但不是错的？不是应该：

T [i]为真当且仅当存在AJ，0 < = j的< = K-1，其中T [j]为TRUE，并且 S（J + 1，K ）是一个有效的单词或S（0，i）是一个有效的单词？

否则，我怎么看不到的表可以从此例如用于字符串来构建：itsthe我们将永远不会有T[2] = true，如果我们不考虑到its是一个字和下一个序列the ie S(2+1, N) for j = 2.
我在这里吗？但是，我们如何才能找到真正的单词？
示例代码我为我的理解作出（s.substring(i,j)从i including j-1返回字符串中的Java）：

int i = 0 
for(; i < s.length(); i++){ 
    for(int j = 0; j > i; j++){ 
     if(T[j] && dictionary.contains(s.substring(j + 1, i)){ 
      T[i] = true; 
      break; 
     } 
    } 
    if(dictionary.contains(s.substring(0, i + 1)){ 
     T[i] = true; 
    } 
}

来源

2013-01-05 Cratylus

你是对所有的更正。

如果你想重建实际的单词添加一个表格数组，它会告诉你最后一个字长你用来设置t[i]到true。让我们称此阵列L[i]

T [i]为真当且仅当存在AJ，0 < = j的< = K-1，其中T [j]为TRUE，并且 S（j + 1，k）是一个有效的单词OR S（0，i）是否是一个有效的单词？ 在第一个的情况下，你在后面设置L[i] = j - L[i] = i。

然后添加你只需要从L[n]，其中n是给定的字符串的总长度递归回结束。

来源

2013-01-05 14:47:55

在'L'是存储在索引或长度是多少？ – Cratylus

@Cratylus索引。然而，因为你只是在分割整个字符串感兴趣，那么这两个在某种程度上是重合的。但是，即使您有兴趣分割可能的最长部分，也可以使用我建议的方法。 –

所以'L [n]'会给出最后一个单词的索引，然后我去'L [n-1]'上一个单词，然后'L [n-2]'等等？ – Cratylus

这取决于你的符号是什么意思，特别是选择子序列。混合方括号和圆括号，“substring [0 ... i]”和“S（j + 1，k）”;我建议我们总是包括左手指数，而不是右手指数。有时通过在左侧使用方括号并在右侧使用圆括号来明确这一点：S [0 ... i）。

如果我们这样做，那么原来的措辞是几乎正确;我和k之间存在一些混淆，我认为这应该是相同的，并且i = 0的情况处理不正确。（与此相关的，我认为当n = 0（空字符串）也不会正确的修改处理。）

Create a table T[N] which says that T[i] is true if the substring S[0...i) 
can be broken into a sequence of valid words. T[i] is true iff i = 0 OR 
(there exists a j, 0<=j<i, where T[j] is true AND S[j...i) is a valid word).

来源

2013-01-05 15:43:12

符号不是我的。我只能假设'[0..i]'是为了包含'i'，因为你指出 – Cratylus

将一串字符分解为有效字

回答

相关问题