139. Word Break - Medium

前往題目

之前寫的文章

想法

• 用trie?

思路

用DP或是Trie

1. 從最後面開始，每個character都向後匹配所有的word並檢查是否一致
2. 一致的話就把當前dp賦值為這個word長度之後的dp，這樣只要是可以順利接上的就會是true，反之如果不是順利接上就會是false(這裡用寫的不清楚，看code會清楚很多)

Code

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);

        dp[s.length()] = true;
        
        // From end to the front (bottom up)
        for (int i = s.length() - 1; i >= 0; --i) {
            // Check every word
            for (String w : wordDict) {
                // 1. In the string's length (enough char to compare)
                // 2. compare if substring equals to the word
                if ( (i + w.length()) <= s.length() 
                && s.substring(i, i + w.length()).equals(w)) {
                    dp[i] = dp[i + w.length()];
                }

                // When the word is able to matched
                if (dp[i]) {
                    break;
                }
            }
        }

        return dp[0];
    }
}

2024/06/25

• 沒寫出來，以為要用雙指針