My solution in JavaScript


  • 0
    S

    My solution is definitely far from perfect and doesn't pass some of the crazier tests due to TLE errors, but I was fairly proud of it and wanted to show it. It uses a k-ary tree approach, which probably made the final sentence constructions more difficult and ugly but otherwise the code reads pretty nicely:

    function TreeNode(text) {
        if (!(this instanceof TreeNode)) return new TreeNode(text)
        this.text = text
        this.children = []
    }
    
    var wordBreak = function(s, wordDict) {
        function toSentences(root, sentence = []) {
            if (root.children.length == 0) {
                if (sentence.reduce((len, word) => { return len + word.length }, 0) + root.text.length === s.length) {
                    return sentences.push(sentence.concat([root.text]).join(' '))
                } else return
            }
            
            root.children.forEach(child => toSentences(child, sentence.concat([root.text])))
        }   
        
        let sentences = []
        
        let forest = makeForest(s, wordDict)
        forest.forEach(root => toSentences(root))
        return sentences
    }
    
    var makeForest = function(s, wordDict) {
        let roots = []
        wordDict.forEach(word => {
            if (s.indexOf(word) == 0) roots.push(TreeNode(word))
        })
        
        roots.forEach(node => {
            node.children = makeForest(s.substr(node.text.length), wordDict)
        })
        
        return roots
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.