【重点】【DP】139.单词拆分

题目

法1：dp

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        word_set = set(wordDict)
        dp = [False] * (n+1) # dp[i]表示s中前i个字符可以由给定的单词组合成功
        dp[0] = True
        for i in range(1, n+1):
            for k in range(i):
                tmp_str = s[k: i]
                if dp[k] and tmp_str in word_set:
                    dp[i] = True
                    break
        
        return dp[n]

Java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[n + 1]; // dp[i]表示s中前i个字符可以由给定的单词组合成功
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int k = 0; k < i; ++k) {
                String tmp = s.substring(k, i);
                if (wordSet.contains(tmp) && dp[k]) {
                    dp[i] = true;
                    break;
                }
             }
        }

        return dp[n];
    }
}