Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words.
Note: From the dictionary B each word can be taken any number of times and in any order.
Example 1:
Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream",
"man", "go", "mango" }
A = "ilike"
Output:
1
Explanation:
The string can be segmented as "i like".
Example 2:
Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream",
"man", "go", "mango" }
A = "ilikesamsung"
Output:
1
Explanation:
The string can be segmented as
"i like samsung" or "i like sam sung".
Your Task:
Complete wordBreak() function which takes a string and list of strings as a parameter and returns 1 if it is possible to break words, else return 0. You don't need to read any input or print any output, it is done by driver code.
Answer :
class Solution
{
bool find_word(vector<string>&b , string a)
{
for(auto i = b.begin() ; i!= b.end() ; i++)
{
if(a == *i)
return true;
}
return false;
}
public:
int wordBreak(string A, vector<string> &B) {
if(A.length() == 0)
{
return 1;
}
for(int i =0 ; i < A.length() ; i++)
{
string p = A.substr(0 , i+1);
if(find_word(B, p))
{
if(wordBreak(A.substr(i+1) , B))
return 1;
}
}
return 0;
}
};
Comments
Post a Comment