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.


jump game leetcode

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 :

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription