139. Word Break | LeetCode Solution
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
andwordDict[i]
consist of only lowercase English letters.- All the strings of
wordDict
are unique.
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<long long int>dp(s.length(),0);
unordered_map<string,int>m;
for(auto i:wordDict)m[i]=1;
for(int i=0; i<s.length(); i++){
int curr=0;
for(int j=0; j<=i; j++){
// cout<<s.substr(j,i-j+1)<<endl;
if(m.find(s.substr(j,i-j+1))!=m.end()){
if(j>0)
curr+=dp[j-1];
else if(j==0)curr+=1;
}
}
// cout<<curr<<endl;
dp[i]=curr;
}
for(auto i:dp)cout<<i<<" ";
return dp[s.length()-1]>0;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.