139. Word Break Leetcode Solution
Word Break Leetcode Problem :
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.
Word Break Leetcode Solution :
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.
Example 1:
- Input: s = “applepenapple”, wordDict = [“apple”,”pen”]
- Output: true
Example 2:
- Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
- Output: false
Intution :
We are using BFS approach as here we are treating the index of string s as a node of graph and we have to traverse from the root to the end node of the graph to find that this substring exists in dictionary or not.
Approach :
- We create an unordered set of wordDict which is given and a visited array to check the character is visited or not and queue.
- Now push 0 as starting element in queue.
- Traverse through queue while q is not empty.
- Store the starting value of queue in a variable to check whether it reaches the end or not and then pop it from queue.
- Then traverse through string from start+1 to the end of the string and check that this character is visited or not.
- If not then find the substring of s from start to i-start and check it is in wordDict or not if yes then push that index to queue and mark visited at that index true.
- Else return false .
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
bool wordBreak(string s, vector< string>& wordDict) {
unordered_set< string>us(wordDict.begin(),wordDict.end());
vector< bool>visited(s.length(),false);
queue< int>q;
q.push(0);
while(!q.empty()){
int start=q.front();
q.pop();
if(start==s.length()){
return true;
}
for(int i=start+1;i<=s.length();i++){
if(visited[i]==true){
continue;
}
if(us.find(s.substr(start,i-start))!=us.end()){
q.push(i);
visited[i]=true;
}
}
}
return false;
}
};class Solution {
public boolean wordBreak(String s, List< String> wordDict) {
Set< String> wordSet = new HashSet(wordDict);
boolean isWord[] = new boolean[s.length() + 1];
isWord[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 0; j < i; j++) {
if (isWord[j] && wordSet.contains(s.substring(j, i))) {
isWord[i] = true;
break;
}
}
}
return isWord[s.length()];
}
}
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp ={"":True}
def valid(curr):
if curr in dp:
return dp[curr]
for i in range(len(curr)-1,-1,-1):
if curr[i:] in wordDict:
dp[curr[i:]] = valid(curr[:i])
if dp[curr[i:]]:
return True
dp[curr]=False
return False
return valid(s)
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment