Back to DSA

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

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumEdit DistancehardUnique Pathsmedium
00:00
import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
Time complexityO(n^2)
Space complexityO(n)