139.md

✏️Leetcode基础刷题之(139. Word Break)

2019-09-05 吴亲库里 库里的深夜食堂

---

✏️描述

给定一个非空字符串以及一个非空的字符串字典，判断给定字符串是否能被分割成一个或者多个字符串字典单词。

---

✏️题目实例

​

✏️题目分析

这道题可以使用动态规划来解.准备好状态的定义以及转移的方程，因为要考虑到空字符，所以定义状态方程的时候0的位置是true，其余暂时都是false，表示当前位置不能切割成字典字符串，不能拆分。dp[i]就表示0到i位置上的子串是否能进行拆分。要判断i位置是否能拆分需要达到两个条件:1是dp[i-1]的位置是可拆分的，2是在字典中寻找截取之后的字符串是否存在于数组中，最后只需要返回dp数组最后一个值是true还是false即可。

  /**
     * @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=$i+1;$j<=strlen($s);++$j){
                if($dp[$i] && in_array(substr($s,$i,$j-$i),$wordDict)){
                    $dp[$j]=true;
                }
            }
        }
        return end($dp);
    }

---

联系

​