# 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 .

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## 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