9 lines Python, 10 lines C++


  • 38

    sentences(i) returns a list of all sentences that can be built from the suffix s[i:].

    Python:

    def wordBreak(self, s, wordDict):
        memo = {len(s): ['']}
        def sentences(i):
            if i not in memo:
                memo[i] = [s[i:j] + (tail and ' ' + tail)
                           for j in range(i+1, len(s)+1)
                           if s[i:j] in wordDict
                           for tail in sentences(j)]
            return memo[i]
        return sentences(0)
    

    C++:

    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        unordered_map<int, vector<string>> memo {{s.size(), {""}}};
        function<vector<string>(int)> sentences = [&](int i) {
            if (!memo.count(i))
                for (int j=i+1; j<=s.size(); j++)
                    if (wordDict.count(s.substr(i, j-i)))
                        for (string tail : sentences(j))
                            memo[i].push_back(s.substr(i, j-i) + (tail=="" ? "" : ' ' + tail));
            return memo[i];
        };
        return sentences(0);
    }

  • 0
    F
    This post is deleted!

  • 0
    L

    Is this O(n4) solution including string operations ?


  • 1
    L

    Thanks Stefan, I've benefited so much from your brilliant solutions in so many different programming questions.


  • 0
    K

    Elegant solution!


  • 5
    T

    it is very elegant,but i do not understand,haha


  • 2
    B

    Very less lines but it take more time to understand than 100 lines code.


  • 0

    It is always a pleasure to see your code.


  • 0
    Y

    a little bit optimization

    class Solution(object):
        def wordBreak(self, s, wordDict):
            memo = {len(s): ['']}
            wordDict=set(wordDict)
            len_w=set(len(w) for w in wordDict)
            def sentences(i):
                if i not in memo:
                    memo[i] = [s[i:i+j] + (tail and ' ' + tail)
                               for j in len_w
                               if s[i:i+j] in wordDict
                               for tail in sentences(i+j)]
                return memo[i]
            return sentences(0)
    

    faster than 95% python solutions


  • 0
    V

    The algorithm of my Go version code is exactly same with your code, but why do I always get TLE? Why does this Go code even slower than python version?

    var (
        dict map[string]struct{}
        memo map[int][]string
        s string
    )
    
    func wordBreak(sh string, wordDict []string) []string {
        dict = make(map[string]struct{})
        for _, v := range wordDict {
            dict[v] = struct{}{}
        }
        s = sh
        memo = make(map[int][]string)
        memo[len(s)] = []string{""}
        return sentences(0)
    }
    
    func sentences(i int) []string {
        if _, ok := memo[i]; !ok {
            for j := i+1; j <= len(s); j++ {
                if _, ok := dict[s[i:j]]; ok {
                    for _, tail := range sentences(j) {
                        if tail == "" {
                            memo[i] = append(memo[i], s[i:j])
                        } else {
                            memo[i] = append(memo[i], s[i:j]+" "+tail)
                        }
                    }
                }
            }
        }
        return memo[i]
    }
    

  • 0
    D

    @V.cholerae I met the same issue when I wrote code in C#


  • 0
    A

    @StefanPochmann said in 9 lines Python, 10 lines C++:

    for j in range(i+1, len(s)+1)

    this line is inefficient. You check for (len(s)-i)*len(wordDict) times

    The better way is to try each word in wordDict directly.


  • 0

    @alan_lannister said in 9 lines Python, 10 lines C++:

    @StefanPochmann said in 9 lines Python, 10 lines C++:

    for j in range(i+1, len(s)+1)

    this line is inefficient. You check for (len(s)-i)*len(wordDict) times

    The better way is to try each word in wordDict directly.

    Nah, the better way is to not change the wordDict from a set to a list.


  • 0
    X

    Your code is always hard to read/understand... care to explain your solution here?


  • 0

    @xela2016 Hmm, not sure what to explain, but I mentioned the meaning of my sentences(i) now.


Log in to reply
 

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