Leetcode 139. Word Break

139. Word Break : 判斷一個字符串能不能由給定的字典中的字符串接得到

Python

方法 : DP求解

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        L = len(s)
        dp = [False]*(L+1)
        dp[0]=True
        for i in range(1,L+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    print(s[j:i])
                    dp[i] = True
        return dp[-1]

C++

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        
        for (int i = 1; i <= n; i++) {
            for (auto word : wordDict) {
                int len = word.size();
                if (len <= i && s.substr(i - len, len) == word) {
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        
        return dp[n];
    }
};