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


2019-9-5 星期四 开始吧


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


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


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


f615cf4213a4ebbc474e014a695d322e.png


题目描述

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


题目分析

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


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D117 599. Minimum Index Sum of Two Lists

>> 下一篇: laravel写B2B电子商务行业门户前端网站系统