Problem Statement:
You are given a word and series of dictionary.
You need to check if the word can be broken down into multiple words that are present in the dictionary
Example
Dictionary { i, like, mobile, ice, cream, mango} Input: ilike Output: Yes The string can be separated as "i like".
Solution
The solution is very simple.
We shall user DP to solve this problem.
We shall create a Boolean DP array of size (length+1).
Then we shall set dp[i] is set to true if it is a valid word.
Then if dp[j] is true, then we check if the substring is present in the dictionary.
Example:
Dict = {"hi", "hello"} ; string = "hihello" ; i = 1 j = 0 j is true substring = h i = 2 j = 1 j = 0 j [0] is true substring = hi i = 3 j = 2 j [2] is true substring = h j = 1 j = 0 j [0] is true substring = hih i = 4 j = 3 j = 2 j [2] is true substring = he j = 1 j = 0 j [0] is true substring = hihe i = 5 j = 4 j = 3 j = 2 j [2] is true substring = hel j = 1 j = 0 j [0] is true substring = hihel i = 6 j = 5 j = 4 j = 3 j = 2 j [2] is true substring = hell j = 1 j = 0 j [0] is true substring = hihell i = 7 j = 6 j = 5 j = 4 j = 3 j = 2 j [2] is true substring = hello
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_set> #include <queue> using namespace std; bool wordBreak(string s, unordered_set<string> &dict) { if(dict.size()==0) return false; vector<bool> dp(s.size()+1, false); dp[0] = true; for(int i=1;i<=s.size();i++) { for(int j=i-1;j>=0;j--) { if(dp[j]) { string word = s.substr(j,i-j); if(dict.find(word)!= dict.end()) { dp[i]=true; break; } } } } return dp[s.size()]; } int main() { unordered_set <string> dict ; dict.insert("hi") ; dict.insert("hello") ; string s = "hihello" ; if(wordBreak(s, dict)) { cout<<"True"<<endl; } else { cout<<"False"<<endl; } return 0; }
Output:
True