Leetcode基础刷题之PHP解析(139. Word Break）

2019-9-5 星期四 开始吧

毕业一年 回家参加高中同学婚礼，给我三个感觉。

1. 一个小伙伴大概经历了人生大事，性格大变，变得很成熟(至少我看来是这样的)。
   
2. 我还是那么幼稚。
3. 完全没读书时聚会的那种感觉 变味了，没有以前的纯粹 无趣
   

上一题链接Leetcode基础刷题之PHP解析(137. Single Number II

题目描述

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

题目分析

这道题可以使用动态规划来解.准备好状态的定义以及转移的方程，因为要考虑到空字符，所以定义状态方程的时候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);
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php