0

我正在尝试了解以下 Java + 动态编程实现（https://pingzhblog.wordpress.com/2015/09/17/word-break/）：

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null) {
            return false;
        }

        boolean[] wordBreakDp = new boolean[s.length() + 1];
        wordBreakDp[0] = true;
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < i; j++) {
                String word = s.substring(j, i);
                if(wordBreakDp[j] && wordDict.contains(word)) {
                    wordBreakDp[i] = true;
                    break;
                }
            }
        }//end for i
        return wordBreakDp[s.length()];
    }
}

String s = "abcxyz"但是需要用and进行一些澄清Set <String> wordDict = ["z", "xy", "ab", "c"]。

我仍然不清楚wordBreakDp[]代表什么，并将其设置为 true 意味着。

所以我做了尝试并得到了wordBreakDP[2,3,5,6]=true，但是这些索引说明了什么？我不能检查一下，i=6因为我们要检查的是最后一个索引是否wordBreakDp[]为真，wordBreakDp[s.length()];？

比如说我得到了abfor s.substring(0, 2);，但是我们怎么能假设下一个循环 ,s.substring(1, 2);没有用，只是break;在循环之外呢？

谢谢

4

4 回答 4

0

这不是一个真正的答案，但它可能有助于理解循环。它在每次迭代时打印 substring(i,j) 和 wordBreakDp[j] 的值。它还在方法结束时打印最终解决方案（分段）。

public boolean wordBreak(String s, Set<String> wordDict) {
    if(s == null) {
        return false;
    }

    boolean[] wordBreakDp = new boolean[s.length() + 1];
    wordBreakDp[0] = true;
    for(int i = 1; i <= s.length(); i++) {
        for(int j = 0; j < i; j++) {

            String word = s.substring(j, i);
            System.out.println("["+j+","+i+"]="+s.substring(j,i)+", wordBreakDP["+j+"]="+wordBreakDp[j]);
            if(wordBreakDp[j] && wordDict.contains(word)) {
                wordBreakDp[i] = true;
                break;
            }
        }
    }//end for i
    for (int i = 1, start=0; i <= s.length(); i++) {
        if (wordBreakDp[i]) {
            System.out.println(s.substring(start,i));
            start = i;
        }
    }
    return wordBreakDp[s.length()];
}
于 2016-11-10T06:20:03.627 回答
0

我想我有你最后一个问题的答案，那就是：

比如说我得到了 s.substring(0, 2); 的 ab，但是我们怎么能假设下一个循环 s.substring(1, 2); 没有用，只是中断了；跳出循环？

你是对的，如果你得到 s.substring(0,2) 的 "ab" 并且你跳出循环，这并不一定意味着 s.substring(1,2) 没有用。假设 s.substring(1,2)很有用。这意味着“a”也是一个有效词，“b”也是如此。该算法找到的解决方案将以“ab”开头，而通过不中断找到的解决方案将是“a”，然后是“b”。这两种解决方案都是正确的（假设字符串的其余部分也可以分解为有效单词）。该算法没有找到所有有效的解决方案。如果字符串可以，它只会返回 true被分解成有效的词，即，如果有一个满足条件的解决方案。当然，可能有不止一种解决方案，但这不是该算法的目的。

于 2016-11-10T16:11:48.507 回答
0 
public class Solution {
    public int wordBreak(String a, ArrayList<String> b) {
        int n = a.length();
        boolean dp[] = new boolean[n+1];
        dp[0] = true;
        for(int i = 0;i<n;i++){
            if(!dp[i])continue;
            for(String s : b){
                int len = s.length();
                int end = len + i;
                if(end > n || dp[end])continue;
                if(a.substring(i,end).equals(s)){
                    dp[end] = true;
                }

            }
        }
        if(dp[n])return 1;
        else return 0;
    }
}
于 2017-12-12T12:59:31.133 回答
0

注意，f[i]表示 的第一个i字符s是否有效。一个例子，

字符串 =catsand

字典 =[cat, cats, sand, and]

 s =     c a t s a n d
dp =   T F F T T F F ?
 i =   0 1 2 3 4 5 6 7
                     *

注意dp[0]是 True，因为空字符串是有效的。说我们已经dp[0]通过了dp[6]。

让我们计算一下dp[7]，它表示是否catsand有效。

为了catsand有效，dict中必须有一个非空的后缀，并且剩余的前缀是有效的。

"catsand" is a valid, if:

  If "" is valid, and "catsand" is inDict, or
  If "c" is valid, and "atsand" is inDict, or
  If "ca" is valid, and "tsand" is inDict, or
  If "cat" is valid, and "sand" is inDict, or
  If "cats" is valid, and "and" is inDict, or
  If "catsa" is valid, and "nd" is inDict, or
  If "catsan" is valid, and "d" is inDict

翻译成伪代码：

dp[7] is True, if:
        j               j  i
  If dp[0] && inDict( s[0..7) ) or
  If dp[1] && inDict( s[1..7) ) or
  If dp[2] && inDict( s[2..7) ) or
  If dp[3] && inDict( s[3..7) ) or
  If dp[4] && inDict( s[4..7) ) or
  If dp[5] && inDict( s[5..7) ) or
  If dp[6] && inDict( s[6..7) )
于 2016-12-02T22:22:56.020 回答