DEV Community

codingpineapple
codingpineapple

Posted on

2 2

LeetCode 139. Word Break (javascript solution)

Description:

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.

Solution:

Time Complexity : O(wordDict.length*s.length^2)
Space Complexity: O(s.length^2)

var wordBreak = function(s, wordDict, memo={}) {
    // If we have s stored in memo return its value
    if(memo[s]!==undefined) return memo[s]
    // We can always make and empty string 
    if(s.length===0) return true   

    for(const word of wordDict) {
        // Check if word is at the beginning of s
        if(s.indexOf(word)===0) {
            // Recursive call to check if using word as the prefix is a possible combination to complete s
            const output = wordBreak(s.slice(word.length), wordDict, memo)
            if(output) {
                // If we are able to complete s save in memo as true
                memo[s] = true
                return true
            }
        }
    }

    // If we get here then we did not find combinations to complete s using wordDict
    memo[s] = false
    return false
};
Enter fullscreen mode Exit fullscreen mode

Image of Stellar post

Check out Episode 1: How a Hackathon Project Became a Web3 Startup 🚀

Ever wondered what it takes to build a web3 startup from scratch? In the Stellar Dev Diaries series, we follow the journey of a team of developers building on the Stellar Network as they go from hackathon win to getting funded and launching on mainnet.

Read more

Top comments (1)

Collapse
 
qurashieman profile image
Tuba Inam •

I found that solution is very popular and helpful : youtube.com/watch?v=_JYE_M3uD-Y