LeetCode 热题 HOT 100Java题解之139. 单词拆分(击败了100%的用户)

2022/1/8 11:03:27

本文主要是介绍LeetCode 热题 HOT 100Java题解之139. 单词拆分(击败了100%的用户),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 题目:

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。


示例:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。



思路:

这里采用动规去做

dp【i】表示的是s的前i位是否可以用wordDict中的单词表示

复杂度:


时间复杂度:双重遍历O(n*n) 

空间复杂度:O(1)

代码:

public boolean wordBreak(String s, List<String> wordDict) {
        //1.建立dp数组 表示i位置是不是可以匹配
        boolean dp[] = new boolean[s.length()+1];

        //2.递推公式 dp[i + word.length()] = true;

        //3.初始化,先全初始化为false,dp[0]空字符串写为true
        Arrays.fill(dp,false);
        dp[0] = true;

        //遍历
        for(int i=0;i<s.length();++i){
            if(!dp[i]){
                //false就跳过下面的语句直接下次循环
                continue;
            }
            for(String word : wordDict){
                //startsWith() 方法用于检测字符串是否以指定的子字符串开始。
                //遍历到的word的长度加上当前dp的长度比s小,并且s的位置以word起始
                if(word.length() + i <= s.length() && s.startsWith(word,i)){
                    dp[i + word.length()] = true;
                }
            }
        }
        return dp[s.length()];
    }

 



这篇关于LeetCode 热题 HOT 100Java题解之139. 单词拆分(击败了100%的用户)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程