题目链接

LeetCode

题目描述

给定一个非空字符串 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

解题思路

方法一：动态规划

139. 单词拆分 - 图1

  1. 初始化 dp = [False,⋯,False]，长度为 n+1 。n 为字符串长度。dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示。
  2. 初始化 dp[0] = True ，空字符可以被表示。
  3. 遍历字符串的所有子串，遍历结束索引 i，遍历区间 [1,n]：

遍历开始索引 j，遍历区间 [0, i) ：
若 dp[j] == true 并且 s[j…i-1] 可以匹配为单词，则 dp[i] = true，
因为 dp[j] == true 代表前 j 个字符可以匹配为单词，也就是 s[0…j-1]
并且 s[j…i-1] 也可以匹配为单词，也就是说 s[0…i-1] 都可以匹配单词，即前 i 个字符都能匹配单词。
即 dp[i] = true 。

  1. class Solution {
  2.     public boolean wordBreak(String s, List<String> wordDict) {
  3.         // 将给定的字典存入哈希表来快速判断
  4.         Set<String> wordDictSet = new HashSet<>(wordDict);
  5.         // dp[i]表示s长度为 i 是是否匹配
  6.         boolean[] dp = new boolean[s.length()+1];
  7.         // 设未匹配时为true，用于后面匹配
  8.         dp[0] = true;
  9.         // s长度从 0 - s.length()
  10.         for(int i = 1; i <= s.length(); ++i){
  11.             // 匹配单词下标从 0 到 i - 1
  12.             for(int j = 0; j < i; ++j){
  13.                 // 如果前面已经匹配并且当前字串可以匹配一个单词，则当前字符串可以拆分单车
  14.                 if(dp[j] && wordDictSet.contains(s.substring(j, i))){
  15.                     dp[i] = true;
  16.                     break;
  17.                 }
  18.             }
  19.         } 
  20.         // 返回整个串是否能拆分单车
  21.         return dp[s.length()];
  22.     }
  23. }
  1. class Solution {
  2.     public boolean wordBreak(String s, List<String> wordDict) {
  3.         char[] arr = s.toCharArray();
  4.         boolean[] dp = new boolean[arr.length];
  5.         int pos = 0;
  6.         while(pos < arr.length){
  7.             if(pos == 0 || dp[pos - 1]){
  8.                 for(String w : wordDict){
  9.                     if(w.length() != 0 && w.charAt(0) == arr[pos]){
  10.                         int tmp = pos, i = 0;
  11.                         while(i < w.length() && tmp < arr.length && w.charAt(i) == arr[tmp]){
  12.                             ++i;
  13.                             ++tmp;
  14.                         }
  15.                         if(i == w.length()){
  16.                             dp[tmp-1] = true;
  17.                         }
  18.                     }
  19.                 }
  20.             }
  21.             ++pos;
  22.         }
  23.         return dp[arr.length - 1];
  24.     }
  25. }
  • 时间复杂度 O(n^2)
  • 空间复杂度 O(n)