139. 单词拆分

题意：

解题思路：

思路：时间复杂度：O(n2)
1. 初始化 dp=[False,~,False]，长度为 n+1。n 为字符串长度，dp[i]表示s的前i位是否可以用wordDict中的单词表示。
2. 初始化 dp[0]=True，空字符可以被表示。
3. 遍历字符串的所有子串，遍历开始索引 i，遍历区间 [1, n)：
    * 遍历结束索引j，遍历区间 [0~i)：
    若 dp[j]=True 且 s[i,⋯,j) 在 wordlist中：dp[i] = True。
    解释：dp[j]=True说明 s 的前 j 位可以用 wordDict表示，则 s[i,⋯,j) 出现在 wordDict 中，说明 s 的前 i 位可以表示。
4. 返回 dp[n]
首先，s[0:4]=='leet' 是wordDict内的单词，所以dp[4]=True。
继续以0为起点，4以后的索引为终点的单词都不在字典内，选择忽略。
即'leetc','leetco','leetcod','leetcode'都不在字典内，忽略不管。
第二步，因为之前设置了DP[4]=True,所以迭代至4为起点
查看后面的单词是否在字典内。发现s[4:8]=='code' 在字典内，
所以设置DP[8]为True，至此循环结束。

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @param String[] $wordDict
     * @return Boolean
     */
    function wordBreak($s, $wordDict) {
        $dp = [0 => true] + array_fill(1, strlen($s), false);
        for ($i = 0; $i < strlen($s); $i++) {
            for ($j = 1; $j <= strlen($s); $j++) {
                if ($dp[$i] && in_array(substr($s, $i, $j - $i), $wordDict)) {
                    $dp[$j] = true;
                }
            }
        }
        return end($dp);
    }
        function wordBreak2($s, $wordDict) {
        $n = strlen($s);
        $dp = array_fill(0, $n + 1, false);
        $dp[0] = true;
        for ($i = 1; $i <= $n; $i++) {
            for ($j = 0; $j < $i; $j++) {
                $word = substr($s, $j, $i - $j);
                if ($dp[$j] && in_array($word, $wordDict)){
                    $dp[$i] = true;
                    break;
                }
            }
        }
        return $dp[$n];
    }
    function wordBreak1($s, $wordDict) {
        $memo = [];
        return $this->helper($s, $wordDict, 0, $memo);
    } 
    function helper($s, $wordDict, $start, &$memo) {
        if ($start == strlen($s)) return true;
        if (isset($memo[$start])) return $memo[$start];
        for ($end = $start + 1; $end <= strlen($s); ++$end) {
            if (in_array(substr($s, $start, $end - $start), $wordDict) && $this->helper($s, $wordDict, $end, $memo)) {
                $memo[$start] = true;
                return true;
            }
        }
        $memo[$start] = false;
        return false;
    }
}

GO代码实现：

func wordBreak(s string, wordDict []string) bool {
    wordDictSet := make(map[string]bool)
    for _, v := range wordDict {
        wordDictSet[v] = true
    }
    dp := make([]bool, len(s) + 1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j<i; j++ {
            if dp[j] && wordDictSet[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}