面试经典算法题75-单词拆分

LeetCode.139

问题描述

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

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

示例 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

思路

1. 定义状态：使用一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以由字典 wordDict 中的单词拼接成。

2. 初始化：dp[0] 设为 true，因为空字符串可以由字典中的单词拼接而成。

3. 状态转移：

   • 对于每个位置 i，检查从位置 j 到 i 的子字符串 s[j:i] 是否在 wordDict 中。

   • 如果 s[j:i] 在 wordDict 中，并且 dp[j] 为 true，则将 dp[i] 设为 true。

4. 返回结果：最终 dp[s.size()] 的值即为答案，表示整个字符串是否可以由字典中的单词拼接成。

参考代码

C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {
    // 将 wordDict 转换为一个 unordered_set，以便快速查找
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    // 创建一个布尔数组 dp，其中 dp[i] 表示 s 的前 i 个字符是否可以由字典中的单词拼接成
    vector<bool> dp(s.size() + 1, false);
    // 初始化 dp[0] 为 true，表示空字符串可以由字典中的单词拼接成
    dp[0] = true;

    // 遍历字符串 s 的每一个字符位置 i
    for (int i = 1; i <= s.size(); ++i) {
        // 遍历所有可能的拆分点 j
        for (int j = 0; j < i; ++j) {
            // 如果 dp[j] 为 true 且 s[j:i] 在字典中，设置 dp[i] 为 true
            if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                dp[i] = true;
                break;  // 找到一个有效的拆分点即可，无需继续检查
            }
        }
    }

    // 返回 dp[s.size()]，表示整个字符串是否可以由字典中的单词拼接成
    return dp[s.size()];
}

int main() {
    string s1 = "leetcode";
    vector<string> wordDict1 = {"leet", "code"};
    cout << "输入: " << s1 << ", 字典: ";
    for (const string& word : wordDict1) {
        cout << word << " ";
    }
    cout << endl;
    cout << "输出: " << (wordBreak(s1, wordDict1) ? "true" : "false") << endl;

    string s2 = "applepenapple";
    vector<string> wordDict2 = {"apple", "pen"};
    cout << "输入: " << s2 << ", 字典: ";
    for (const string& word : wordDict2) {
        cout << word << " ";
    }
    cout << endl;
    cout << "输出: " << (wordBreak(s2, wordDict2) ? "true" : "false") << endl;

    string s3 = "catsandog";
    vector<string> wordDict3 = {"cats", "dog", "sand", "and", "cat"};
    cout << "输入: " << s3 << ", 字典: ";
    for (const string& word : wordDict3) {
        cout << word << " ";
    }
    cout << endl;
    cout << "输出: " << (wordBreak(s3, wordDict3) ? "true" : "false") << endl;

    return 0;
}

Java

import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class WordBreak {

    public static boolean wordBreak(String s, List<String> wordDict) {
        // 将 wordDict 转换为一个 HashSet，以便快速查找
        Set<String> wordSet = new HashSet<>(wordDict);
        // 创建一个布尔数组 dp，其中 dp[i] 表示 s 的前 i 个字符是否可以由字典中的单词拼接成
        boolean[] dp = new boolean[s.length() + 1];
        // 初始化 dp[0] 为 true，表示空字符串可以由字典中的单词拼接成
        dp[0] = true;

        // 遍历字符串 s 的每一个字符位置 i
        for (int i = 1; i <= s.length(); i++) {
            // 遍历所有可能的拆分点 j
            for (int j = 0; j < i; j++) {
                // 如果 dp[j] 为 true 且 s[j:i] 在字典中，设置 dp[i] 为 true
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一个有效的拆分点即可，无需继续检查
                }
            }
        }

        // 返回 dp[s.length()]，表示整个字符串是否可以由字典中的单词拼接成
        return dp[s.length()];
    }

    public static void main(String[] args) {
        String s1 = "leetcode";
        List<String> wordDict1 = List.of("leet", "code");
        System.out.println("输入: " + s1 + ", 字典: " + wordDict1);
        System.out.println("输出: " + wordBreak(s1, wordDict1));

        String s2 = "applepenapple";
        List<String> wordDict2 = List.of("apple", "pen");
        System.out.println("输入: " + s2 + ", 字典: " + wordDict2);
        System.out.println("输出: " + wordBreak(s2, wordDict2));

        String s3 = "catsandog";
        List<String> wordDict3 = List.of("cats", "dog", "sand", "and", "cat");
        System.out.println("输入: " + s3 + ", 字典: " + wordDict3);
        System.out.println("输出: " + wordBreak(s3, wordDict3));
    }
}

Python

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> bool:
    # 将 wordDict 转换为一个 set 以便快速查找
    wordSet = set(wordDict)
    # 创建一个布尔数组 dp，其中 dp[i] 表示 s 的前 i 个字符是否可以由字典中的单词拼接成
    dp = [False] * (len(s) + 1)
    # 初始化 dp[0] 为 True，表示空字符串可以由字典中的单词拼接成
    dp[0] = True

    # 遍历字符串 s 的每一个字符位置 i
    for i in range(1, len(s) + 1):
        # 遍历所有可能的拆分点 j
        for j in range(i):
            # 如果 dp[j] 为 True 且 s[j:i] 在字典中，设置 dp[i] 为 True
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break  # 找到一个有效的拆分点即可，无需继续检查

    # 返回 dp[len(s)]，表示整个字符串是否可以由字典中的单词拼接成
    return dp[len(s)]

# 测试用例
if __name__ == "__main__":
    s1 = "leetcode"
    wordDict1 = ["leet", "code"]
    print(f"输入: {s1}, 字典: {wordDict1}")
    print(f"输出: {wordBreak(s1, wordDict1)}")

    s2 = "applepenapple"
    wordDict2 = ["apple", "pen"]
    print(f"输入: {s2}, 字典: {wordDict2}")
    print(f"输出: {wordBreak(s2, wordDict2)}")

    s3 = "catsandog"
    wordDict3 = ["cats", "dog", "sand", "and", "cat"]
    print(f"输入: {s3}, 字典: {wordDict3}")
    print(f"输出: {wordBreak(s3, wordDict3)}")