9 lines Python, 10 lines C++


  • 40

    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


  • 3
    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


  • -1
    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.


  • 2
    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.


  • 0
    X

    @StefanPochmann
    Hi Stefan, I've tried to rewrite your code as follows:

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

    I only got ["cats and dog"] not the expected answer ["cat sand dog","cats and dog"]. How can I correct this? How can I append all the possible results? Thank you.


  • 1
    A

    @x9W6y
    You need to append to list as the list comprehension in OP, not override it.

    class Solution(object):
        def wordBreak(self, s, wordDict):
            memo = {len(s): ['']}
            def sentences(i):
                if i not in memo:
                    memo[i] = []
                    for j in range(i+1, len(s)+1):
                        if s[i:j] in wordDict:
                            for tail in sentences(j):
                                if tail != '':                                
                                    memo[i].append( s[i:j] + ' ' + tail)
                                else:
                                    memo[i].append( s[i:j] )
                return memo[i]
            return sentences(0) 
    

  • 0
    A

    @StefanPochmann
    Since wordDict changed to list, the Python solution slows down from 60ms to 272ms. Can you add one line in your Python to convert it to set?

    wordDict = set(wordDict)
    

    or we need to try words in wordDict instead of loop over range(i+1, len(s)+1). Same 61ms.

        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: List[str]
            """
            m = {'': ['']}
    
            def DFS(s):
                if s not in m:
                    m[s] = [
                        word + (tail and ' '+tail)
                        for word in wordDict
                        if s.startswith(word)
                        for tail in DFS(s[len(word):])
                    ]
                return m[s]
    
            return DFS(s)
    

  • 0
    X

    @algowl
    Thank you so much!


  • 0
    Z

    2 liner, just kidding...

    class Solution(object):
        def wordBreak(self, s, wordDict):
            search = lambda i, wordDict, cache={len(s): [[]]}: cache[i] if i in cache else [[s[i: j]] + r for j in xrange(i + 1, len(s) + 1) if s[i: j] in wordDict for r in cache.setdefault(j, search(j, wordDict))]
            return map(lambda x: ' '.join(x), search(0, set(wordDict)))

Log in to reply
 

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