Word Break - Easy Concise DP

Array     C++     Dynamic Programming     Hash Table     Medium     Memoization     String     Trie    

Problem Statement:

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.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

 

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 the strings of wordDict are unique.

Solution:

The overall idea is that we maintain a dp array of dtype bool which denotes whether it is possible for string ending at i. The recursive relation is:

 
dp[i] = True if any (dp[j] = True and s[j:i] is in wordDict for j in 0..i)
Else dp[i] = False
 

C++ code:

 
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string>words;
        for (string w: wordDict) words.insert(w);
        int n=s.length();
        
        vector<bool>valid(n+1,false);
        valid[0] = true;
        
        for (int j=1; j<=n; j++)
        {
            bool curr = false;
            for (int i=0; i<j; i++)
            {
                string sub(s.begin()+i, s.begin()+j);
                if (valid[i] && words.count(sub)){curr=true; break;}
            }
            valid[j] = curr;
        }
        return valid[n];
    }
};