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"ありSet <String> wordDict = ["z", "xy", "ab", "c"]ます。

何が何を表しているのかはまだ不明wordBreakDp[]であり、1 つを true に設定することは意味します。

だから私は試みて得ましたがwordBreakDP[2,3,5,6]=true、それらのインデックスは何を教えてくれますか? i=6チェックしているのは の最後のインデックスwordBreakDp[]が true であるかどうかだけなので、チェックできなかったのwordBreakDp[s.length()];でしょうか?

たとえば、 を取得abしたとしますが、次のループが役に立たず、ループの外にあるとs.substring(0, 2);どのように仮定できるでしょうか?s.substring(1, 2);break;

ありがとうございました

4

4 に答える 4

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を返すだけですつまり、条件を満たす解が 1 つある場合です。もちろん、複数の解があるかもしれませんが、それはこのアルゴリズムの目的ではありません。

于 2016-11-10T16:11:48.507 に答える
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 に答える