写点什么

头脑风暴:单词拆分

  • 2022 年 8 月 09 日
    江苏
  • 本文字数:990 字

    阅读完需:约 3 分钟

头脑风暴:单词拆分

题目

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


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


示例 1:


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


示例 2:


输入: s = "applepenapple", wordDict = ["apple", "pen"]输出: true解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。     注意,你可以重复使用字典中的单词。
复制代码


示例 3:


输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出: false
复制代码

解题方法

根据题意,此题可把单词比作物品,字符串 s 就是背包,单词能否组成字符串 s,就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词,说明就是一个完全背包!


所以求解思路如下:


第一步,确定 dp 数组以及下标的含义,dp[i] : 字符串长度为 i 的话,dp[i]为 true,表示可以拆分为一个或多个在字典中出现的单词。


第二步,确定递推公式:如果确定 dp[j] 是 true,且 [j, i] 这个区间的子串出现在字典里,那么 dp[i]一定是 true(j < i )。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是 true) 那么 dp[i] = true。


第三步,dp 数组初始化:dp[i] 的状态依靠 dp[j]是否为 true,那么 dp[0]就是递归的根基,dp[0]一定要为 true,否则递归下去后面都都是 false 了

代码实现

class Solution {    public boolean wordBreak(String s, List<String> wordDict) {        Set<String> wordDictSet = new HashSet(wordDict);        boolean[] dp = new boolean[s.length() + 1];        dp[0] = true;        for(int i = 1; i <= s.length(); i++){            for(int j = 0; j < i; j++){                if(dp[j] && wordDictSet.contains(s.substring(j, i))){                    dp[i] = true;                    break;                }            }        }        return dp[s.length()];    }}
复制代码

最后

  • 时间复杂度:O(n^2),其中 nn 为字符串 s 的长度。我们一共有 O(n) 个状态需要计算,每次计算需要枚举 O(n) 个分割点,哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间,因此总时间复杂度为 O(n^2)。

  • 空间复杂度:O(n),其中 n 为字符串 s 的长度。

发布于: 刚刚阅读数: 3
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
头脑风暴:单词拆分_算法_HelloWorld杰少_InfoQ写作社区