Example 1: Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: "applepenapple" can be seperated as "apple pen apple".
This problem can be solved by using DP [Dynamic Programming].
We shall have a look at the code, before explaining the code.
Solution in C++
#include<iostream> #include<unordered_set> #include<vector> #include<string> using namespace std; bool wordBreak(string s, unordered_set<string>& wordDict) { int n = s.length(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i ++) { for (int j = 0; j < i; j ++) { //cout<<"i = "<< i << " j = "<< j<< " s.substr(j, i - j) = "<< s.substr(j, i - j)<<endl; dp[i] = dp[j] && wordDict.count(s.substr(j, i - j)); if (dp[i]) { //cout<<"Came to break ======= "<<endl; break; } } } return dp[n]; } int main() { string str = "appleandapple"; unordered_set<string> dict = {"apple", "and"}; if(wordBreak(str, dict)) cout<<"Present"<<endl; else cout<<"Not Present"<<endl; return 0; }
Output:
Present
Explanation:
From the code above, we use a Boolean vector to hold the truth value.
The first dp[0] is set to true, as it will help us to find the first sub-string if it exist.
Then we start filling the Boolean vector dp with the appropriate vavlue.
If a dp[i] value is true, then the sub string from dp[0] tp dp[i] is present in the dictionary.
Then we start our search from dp[i+1] to end.
In our example s = “appleandapple” and dict = {apple, and}
When i = 5, j = 0 and we get the word = “apple”.
We will set dp[5] = true.
At the end of the loop, the Boolean vector output will be:
1 0 0 0 0 1 0 0 1 0 0 0 0 1
It can be mapped to our example as shown in the diagram below:
In the end we take the value of dp[string_length] getting out result.