Practice/Microsoft/Leetcode 139. Word Break

Leetcode 139. Word Break

CodingMust

Problem

You are given a string s and a list of words wordDict. Your task is to determine whether the entire string can be constructed by concatenating words from the dictionary in sequence. Words from the dictionary may be reused multiple times, and each word must be used completely (no partial matching).

Return true if the string can be fully composed using dictionary words, otherwise return false.

Requirements

1. The string must be completely covered by concatenated dictionary words
2. Dictionary words can be reused any number of times
3. The order of characters in the string must be preserved
4. Each dictionary word must match a contiguous substring when used

Constraints

• 1 ≤ s.length ≤ 300
• 1 ≤ wordDict.length ≤ 1000
• 1 ≤ wordDict[i].length ≤ 20
• s and wordDict[i] consist of only lowercase English letters
• All words in wordDict are unique

Examples

Example 1:

Input: s = "applepen", wordDict = ["apple", "pen"] Output: true Explanation: The string can be segmented as "apple" + "pen"

Example 2:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false Explanation: Even though we have "cats", "and", "dog" in the dictionary, we cannot form "catsandog" because after "cats" we have "andog" which cannot be formed from available words

Example 3:

Input: s = "catcatcat", wordDict = ["cat"] Output: true Explanation: We can reuse "cat" three times to form the complete string