139. Word Break

问题

这个问题描述的是我们有一个字符串s，和一个字符数组wordDict，让确定下是否这个字符串由数组中的字符串组成，一个数组中的字符串可以多次出现在s中。

解析

这个题目比较简短，也比较清晰。问题是怎么去想这个问题。

我的思路一开始也没有说马上想出来一个方法，就先去跑了一个case：

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

跑case的过程是这样的，我们应该先从一个字符看是否存在于wordDict，然后看两个字符，三个，四个，这时leet存在于wordDict了，那我们就会看剩下的部分是否也存在于字符串数组中。

这个地方体现了一个与的关系，当我们遍历数组到index 为i的时候，那么我们需要看的是前i个字符是否是满足条件的（即截止到i是否为true），以及i之后的字符是否存在于数组中。

这个题到这，差不多应该可以看出我们是自底向上从子问题去一步步推到到整个字符串。先解决长度为1 的子字符串的问题，然后长度依次增加，直到最后的s。

所以这个题你一开始想着想着甚至把代码写出来了才发现他很契合动态规划题目的模式。子问题，状态转移等等。

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int m = s.length();
        int n = wordDict.size();
        boolean[] dp = new boolean[m + 1];
        dp[0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[m];
    }
}

Problem

This problem describes that we have a string s, and an array of characters wordDict, let determine if the string consists of strings in the array, and a string in the array can appear multiple times in s.

Parsing

This topic is relatively short and clear. The question is how to think about it.

I didn't start my thought process by saying I'd come up with a method right away, so I went ahead and ran a case of.

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

The process of running the case is like this, we should start with one character to see if it exists in wordDict, then look at two characters, three, four, when leet exists in wordDict, then we will see if the rest of it also exists in the string array.

This place reflects a relationship with, when we traverse the array to the index of i, then we need to see whether the first i characters are to meet the conditions (that is, whether the cutoff to i is true), and whether the characters after i exist in the array.

By this point in the problem, it should be almost obvious that we are pushing from the bottom up from the subproblem to the whole string step by step. First, we solve the substring of length 1, and then the length increases sequentially until the final s.

So this is a problem that you start to think about and even write out the code before you realize that it fits the pattern of dynamic programming topics. Subproblems, state shifting, etc.

Code

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int m = s.length();
        int n = wordDict.size();
        boolean[] dp = new boolean[m + 1];
        dp[0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[m];
    }
}