Create a boolean DP table where dp[i] is true when the first i characters of s form a valid decomposition.

Word Break

medium

Acceptance: 45%

Dynamic Programming

Given a string s and a collection of dictionary words, decide whether s can be decomposed into a sequence of one or more words that all appear in the dictionary. Each dictionary word may be used more than once.

Examples

Example 1:

Input:s = "applepenapple", wordDict = ["apple","pen"]

Output:true

Explanation: "applepenapple" splits into "apple" + "pen" + "apple".

Example 2:

Input:s = "pineapplepen", wordDict = ["pine","apple","pen","pineapple"]

Output:true

Explanation: Can be split as "pineapple" + "pen" or "pine" + "apple" + "pen".

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Word Break

Examples

Hints

Related Problems