题解

题面描述

给定一个字符串$s$`和一个字符串列表$wordDict$作为字典，要求判断是否可以利用字典中出现的一个或多个单词拼接出字符串$s$。
注意：

• 不要求字典中出现的单词全部都使用。
• 字典中的单词可以重复使用。

例如，

• 当 $s$ = "leetcode"，$wordDict$ = ["leet", "code"] 时，返回 $true$。
• 当 $s$ = "applepenapple"，$wordDict$ = ["apple", "pen"] 时，返回 $true$。
• 当 $s$ = "catsandog"，$wordDict$ = ["cats", "dog", "sand", "and", "cat"] 时，返回 $false$。

思路

我们可以使用动态规划来解决该问题。

• 定义一个长度为 $n+1$ 的布尔数组 $dp$，其中 $n$ 是字符串 $s$ 的长度。
• $dp[i]$ 表示字符串 $s[0..i-1]$ 是否可以被分割成字典中的单词。
• 初始状态 $dp[0] = true$（空串可以被认为是被成功分割的）。
• 对于每个位置 $i$，我们遍历 $j$ 从 $0$ 到 $i-1$，若 $dp[j]$ 为 $true$ 且子串 $s[j..i-1]$ 在 $wordDict$ 中，则令 $dp[i] = true$。
• 最后检查 $dp[n]$ 是否为 $true$。

该方法的时间复杂度为 $O(n^2)$（假设查找字典中的单词为 $O(1)$），符合题目规模要求。

代码分析

• 变量说明：
  • $s$：输入的目标字符串。
  • $wordDict$：字典列表。
  • $dp$：动态规划数组，大小为 $n+1$。
• 算法步骤：
  1. 初始化 $dp[0] = true$。
  2. 遍历字符串的每个位置 $i$，并尝试所有可能的分割位置 $j$，若 $dp[j]$ 为 $true$ 且 $s[j..i-1]$ 在字典中，则将 $dp[i]$ 置为 $true$。
  3. 最后输出 $dp[n]$ 的值。

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>
using namespace std;

class Solution {
public:
    // 判断字符串 s 是否可以由 wordDict 中的单词拼接而成
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true; // 空串可以被成功拼接

        // 遍历字符串每个位置
        for (int i = 1; i <= n; i++) {
            // 枚举分割点 j，判断 s[j...i-1] 是否在字典中
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break; // 一旦找到一种切分方式，退出当前循环
                }
            }
        }
        return dp[n];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    getline(cin, s); // 读取字符串 s

    string dictLine;
    getline(cin, dictLine); // 读取字典字符串
    istringstream iss(dictLine);
    string word;
    unordered_set<string> wordDict;
    // 将输入的单词存入集合中
    while(iss >> word){
        wordDict.insert(word);
    }
    
    Solution solution;
    // 输出结果
    cout << (solution.wordBreak(s, wordDict) ? "true" : "false");
    
    return 0;
}

Python

class Solution:
    def wordBreak(self, s: str, wordDict: set) -> bool:
        n = len(s)
        # dp[i] 表示 s[0:i] 是否可以被切分成字典中的单词
        dp = [False] * (n + 1)
        dp[0] = True  # 空串可以被成功切分
        
        # 遍历字符串每个位置
        for i in range(1, n + 1):
            # 枚举所有可能的切分点 j
            for j in range(i):
                # 如果 s[j:i] 在字典中且 s[0:j] 可以切分，则 s[0:i] 可切分
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break  # 找到一种切分方式即可退出循环
        return dp[n]

if __name__ == '__main__':
    import sys
    # 从标准输入读取数据
    s = sys.stdin.readline().strip()
    dict_line = sys.stdin.readline().strip()
    word_list = dict_line.split()
    wordDict = set(word_list)
    
    solution = Solution()
    result = solution.wordBreak(s, wordDict)
    print("true" if result else "false")

Java

import java.util.*;
import java.io.*;

public class Main {
    static class Solution {
        // 判断字符串 s 是否可以由 wordDict 中的单词拼接而成
        public boolean wordBreak(String s, Set<String> wordDict) {
            int n = s.length();
            // dp[i] 表示 s.substring(0, i) 是否可以被切分
            boolean[] dp = new boolean[n + 1];
            dp[0] = true; // 空串可以成功切分
            
            // 遍历字符串每个位置
            for (int i = 1; i <= n; i++) {
                // 枚举所有可能的分割位置 j
                for (int j = 0; j < i; j++) {
                    // 如果 s.substring(j, i) 在字典中且 dp[j] 为 true，则 dp[i] 置为 true
                    if (dp[j] && wordDict.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break; // 找到一种切分方式即可退出当前循环
                    }
                }
            }
            return dp[n];
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 进行输入输出，符合 ACM 模式
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim(); // 读取字符串 s
        String dictLine = br.readLine().trim(); // 读取字典字符串
        
        // 将字典字符串拆分为单词，并存入集合中
        String[] words = dictLine.split("\\s+");
        Set<String> wordDict = new HashSet<>();
        for(String word : words) {
            wordDict.add(word);
        }
        
        Solution solution = new Solution();
        boolean result = solution.wordBreak(s, wordDict);
        // 输出结果
        System.out.println(result ? "true" : "false");
    }
}

Leetcode 86.单词拆分-原题链接

题目内容

给你一个字符串 $s$ 和一个字符串列表 $wordDict$ 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 $s$ 则返回 $true$。

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

输入描述

第一行一个字符串$s$ 第二行一个字符串列表$wordDict$作为字典

输出描述

如果可以利用字典中出现的一个或多个单词拼接出 $s$ 则返回 $true$。否则返回$false$

样例1

输入

leetcode
leet code

输出

true

说明

返回 $true$ 因为 "$leetcode$" 可以由 "$leet$" 和 "$code$" 拼接成。

样例2

输入

applepenapple
apple pen

输出

true

说明

返回 $true$因为 "$applepenapple$" 可以由 "$apple$" "$pen$" "$apple$" 拼接成。

注意，你可以重复使用字典中的单词。

样例3

输入

catsandog
cats dog sand and cat

输出

false

提示：

• $1 <= s.length <= 300$
• $1 <= wordDict.length <= 1000$
• $1 <= wordDict[i].length <= 20$
• $s$和 $wordDict[i]$仅由小写英文字母组成
• $wordDict$中的所有字符串互不相同