leetcode
leet code

true

applepenapple
apple pen

true

catsandog
cats dog sand and cat

false

#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;
}

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")

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");
    }
}