[Vssue]0139.单词拆分.md

[youngyangyang04]

https://www.programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html

[Du1in9]

Set<String> hash = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;

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

// 例: s = "abba", wordDict = ["a", "bb"]
i = 1: dp = [1, 0, 0, 0, 0]
    j = 0: dp[0] = 1, hash.contains("a") = 1, dp[1] = 1 (放"a")
i = 2: dp = [1, 1, 0, 0, 0]
    j = 0: dp[0] = 1, hash.contains("ab") = 0, 继续遍历
    j = 1: dp[1] = 1, hash.contains("b") = 0, 结束遍历
i = 3: dp = [1, 1, 0, 0, 0]
    j = 0: dp[0] = 1, hash.contains("abb") = 0, 继续遍历
    j = 1: dp[1] = 1, hash.contains("bb") = 1, dp[3] = 1 (放"bb")
i = 4: dp = [1, 1, 0, 1, 0]
    j = 0: dp[0] = 1, hash.contains("abba") = 0, 继续遍历
    j = 1: dp[1] = 1, hash.contains("bba") = 0, 继续遍历
    j = 2: dp[2] = 0, 继续遍历
    j = 3: dp[3] = 1, hash.contains("a") = 1, dp[4] = 1 (放"a")