0

这基本上是重复的:

如何将字符串拆分为单词。例如:“stringintowords”->“String Into Words”?

neverthelees,我在使用中使用了一个函数,例如:public int Word(x) {code},对于字符串 x,它将返回一个整数(+ve 或 -ve),并且该整数将指示分区对于特定单词的好坏程度. 我应该返回给出最大数量的组合。

我想为此做的是创建一个 table(i,j) ,其中 i 和 j 具有单词的长度,并在 tern 中填写表格,如:

for i = 1 to n
   for j=i to n do 
      word(subset of x i to j)

并填写表格,但是,我到底如何才能检索到最佳解决方案(以递归方式?)

任何帮助表示赞赏。

编辑:最佳路径是 word(x) 函数总和最高的路径,即如果我们有
一个 path(1,3)=10 , (3,6)=20, (6,7)=1 和
路径 (1,1)=0 , (2,5)=12, (5,7)=-1
然后第一条路径的总和 > 2nd

EDIT2:我希望每个人都知道,经过长时间的工作,我已经回答了这个问题,不要介意没有得到解决方案,我想自己得到它总是最好的:P

干杯!:)

4

2 回答 2

0

好的,让我举个例子:

word thetree


         1  2   3  4  5  6  7 ( ending index)

start 1  1  -1  2 -1 -1 -1 -1
      2  0  1  -1  -1 -1 -1 -1
      3  0  0   1  0  0  0  0
      4  0  0   0  1  0  0  4
      5  0  0   0  0  1  0  0
      6  0  0   0  0  0  1  0  
      7  0  0   0  0  0  0  1

好好考虑这个解决方案,然后如果你单独存储每个列,那么在第 3 列你得到 2,在第 7 列你得到 4,总共有 6,但是,如果你分别取每个字母,那么:1+1+ 1+1+1+1+1= 7 (对角线向下 i=j) 这意味着 talbe 不正确...

如果我只能存储上一个最佳输入的位置,这可能会起作用。(我再次认为)

于 2010-12-05T01:18:37.993 回答
0

山姆,你是说:

如果有一个长度为 j 的子字符串,则您有一个表格,其中填充了您在字符串中的位置,以及每个单元格的布尔值。

例子:

                    |       Positions of the example:
                    |            "xdeafcatmonologue"
 -------------------|-------------01234567890123476----------------
length of substring |                              
        1           |             11111111111111111     
        2           |             ------2----------
        3           |             -----3------3----
        4           |             -4--------------- 
        5           |             -----------------
        6           |             -----------------
        7           |             -----------------
        8           |             -----------------
        9           |             --------9--------
                    |              

      final         |             -4---3--9---3----

破折号在技术上是零,数字势能,这是您将构建的表格。

如果您只存储每个位置的最大值,您可以构建一个小得多的表,因为您的 Word 函数会告诉您每个位置的最大值。如果您迭代子字符串大小、变量 j 并不重要,因为 Word 不使用 j。

如果我对这些假设有误,请纠正我。

于 2010-12-04T23:59:48.500 回答