Programming

Leetcode-139. Word Break

By PattySung 02 February 2024
Leetcode-139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”,“code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”. Example 2:

Input: s = “applepenapple”, wordDict = [“apple”,“pen”] Output: true Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Note that you are allowed to reuse a dictionary word.

<解題一> Dp + hashSet存單詞


class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for(int i = 0; i < s.length(); i++){
            for(int j = i+1; j <= s.length(); j++){
                if(dp[i] && wordDictSet.contains(s.substring(i,j))){
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

T: O(n^2 * m) S: O(n + m * k)，m 是字典中單詞的最大長度，k 是單詞的平均長度。

<解題二> Dp + 直接看是否有對應的word長度


class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for(int i = 0; i < s.length(); i++){
            if(!dp[i]) continue;

            for(String word : wordDict){
                int j = i + word.length();
                if(j <= s.length() && s.substring(i,j).equals(word)){
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}