My solution using Python


  • 4
    E

    I used a Trie to store all the dict words, and then for every position i in s, find those position(s) ed so that [st, ed) is a dict word.

    After that is basiclly a search problem, simply using dfs (or you can call it memorized search) to check whether from position i we can divide s[i:] with dict words.(say this array is called v, and v[i] = True if s[i:] is dividable.

    If v[0] is True, then find all the solutions using recurse.

    Here is my code using Python.

    class Node:
    	def __init__(self):
    		self.next = [ None for i in range(26) ]
    		self.mark = False
    
    class Solution:
    	# @param s, a string
    	# @param dict, a set of string
    	# @return a list of strings
    	def insert(self, word):
    		p = self.root
    		for s in word:
    			k = ord(s) - ord('a')
    			if p.next[k] == None:
    				p.next[k] = Node()
    			p = p.next[k]
    		p.mark = True
    
    	def build(self, s, st):
    		n = len(s)
    		p = self.root
    		for i in range(st, n):
    			if p == None:
    				return 
    			k = ord(s[i]) - ord('a')
    			if p.next[k] == None:
    				return
    			p = p.next[k]
    			if p.mark:
    				self.g[st].append(i + 1)    # [st, i + 1) is a word in dict
    	def path(self, st):
    		if st == self.n:
    			self.v[st] = 1
    			return 1
    		if self.v[st] != -1:
    			return self.v[st]
    		for ed in self.g[st]:
    			if self.path(ed):
    				self.v[st] = 1
    		if self.v[st] == -1:
    			self.v[st] = 0
    		return self.v[st]
    
    	def get(self, st):
    		if st == self.n:
    			return []
    		res = []
    		for ed in self.g[st]:
    			if self.v[ed] == 1:
    				tmp = self.get(ed)
    				ss = self.s[st:ed]
    				for sp in tmp:
    					res.append(ss + ' ' + sp)
    				if tmp == []:
    					res.append(ss)
    		return res
    
    	def wordBreak(self, s, dict):
    		n = len(s)
    		self.root = Node()
    		self.n = n
    		self.s = s
    		#self.dict = dict
    		self.g = [ [] for i in range(n + 1) ]
    		self.v = [ -1 for i in range(n + 1) ]
    		for word in dict:
    			self.insert(word)
    		for i in range(n):
    			self.build(s, i)
    		ok = self.path(0)
    		ret = []
    		if ok == 1:
    			ret = self.get(0)
    		return ret

  • 0
    C

    My Python solution

    import sys
    import pdb
    
    
    class Solution():
        # @param s, a string
        # @param dict, a set of string
        # @return a list of strings
        def wordBreak(self, s, d, curr_sentance=""):
            # pdb.set_trace()
            # quick check whether all chars will match (only at the begining)
            if not curr_sentance:
                sentance_chars = set(s)
                dict_chars = set("".join(list(d)))
                if not sentance_chars.issubset(dict_chars):
                    return []
            if not s and curr_sentance:
                return [curr_sentance.rstrip()]
            sentances = []
            for ditem in d:
                if s.startswith(ditem):
                    sentance = self.wordBreak(s[len(ditem):], d,
                                              curr_sentance + ditem + " ")
                    if sentance:
                        sentances += sentance
    
            return sentances
    
    
    # main ()
    def main():
        ph = "aaaaaaa"
        d = {"aaaa", "aa", "a"}
        s = Solution()
        print "{}".format('\n'.join(s.wordBreak(ph, d)))
        return 0
    
    if __name__ == "__main__":
        sys.exit(main())
    

  • 0
    R

    Another python solution, this time recursive and with failures memorizations to linearize the
    time complexity.

    Assumes that the dictionary is huge, while the text is relatively small, is it a real case? We don't know.
    There is a defect that I didn't fixed, I recalculate the max word size in the dictionary each time, this can
    be done just once.

    Runs in 140ms, I would like to know about your solutions.

    def _wordBreak(source, dictionary, failures, pos):
        """Splits a given text into words contained into a dictionary.
    
        Recursive solution:
        - memoizes the failures in order to avoid exponential time complexity (dynamic programming)
        - first tries to match longest word in order to further reduce the number of combinations
        """
    
        # Looks inside memoized failures to avoid exponential execution:
        if pos in failures:
            return None
    
        results = []
    
        # The entire source may be contained inside the dictionary:
        if source in dictionary:
            results.append([source])
    
        # Max word size:
        size = max(map(len, dictionary))   # Traverses the dictionary and looks for the longest word
        size = min(len(source) - 1, size)  # Leaves at least one character for the tail.
    
        # Tries with part of the source, first with longer ones:
        while size > 0:
    
            # Splits the source into two parts, head and tail:
            head, tail = source[:size], source[size:]
    
            # If head is not in the dictionary skips current case:
            if head not in dictionary:
                #failures.add(pos + size)
                size -= 1
                continue
    
            # Continues with the tail:
            tailResults = _wordBreak(tail, dictionary, failures, pos + size)
            if not tailResults:
                size -= 1
                continue  # No solutions, skips current case.
    
            # Collects the results after prepending the head to them:
            for result in tailResults:
                result.insert(0, head)
                results.append(result)
    
            # Tries with smaller words:
            size -= 1
    
        # On failure, memoizes it:
        if len(results) == 0:
            failures.add(pos)
            return
    
        return results
    
    
    class Solution:
        """A solution for our problem."""
    
        def wordBreak(self, text, dictionary):
            """Splits a given text into words contained into a dictionary.
    
            Returns a list of all possible solutions.
            """
    
            if len(dictionary) == 0:
                return []
    
            results = _wordBreak(text, dictionary, set(), 0)
            if not results:
                return []
    
            return [" ".join(result) for result in results]

  • 0
    R

    Another similar solution, but by embedding the recursion inside the class I obtained a slightly faster implementation, looks like that the recursive call is a bottleneck here, since now I just pass less parameters each recursion.

    I also keep the max word size in the dictionary precalculated, but alone was not giving performance benefits, there was a regression because the extra parameter passed.

    class Solution:
        """A solution for our problem."""
    
        def __init__(self):
            self.dictionary = set()
            self.dictionaryMaxLen = 0
            self.failures = set()
    
        def wordBreak(self, text, dictionary):
            """Splits a given text into words contained into a dictionary.
    
            Returns a list of all possible solutions.
            """
    
            if len(dictionary) == 0:
                return []
    
            # Prepares the object for the recursive execution:
            self.dictionary = dictionary
            self.dictionaryMaxLen = max(map(len, dictionary))
            self.failures = set()
    
            results = self._wordBreak(text, 0)
            if not results:
                return []
    
            return [" ".join(result) for result in results]
    
        def _wordBreak(self, source, pos):
            """Splits a given text into words contained into a dictionary.
    
            Returns a list of all possible solutions or None in case of failure.
    
            Recursive solution:
            - memoizes the failures in order to avoid exponential time complexity (dynamic programming)
            - first tries to match longest word in order to further reduce the number of combinations
            """
    
            # Looks inside memoized failures to avoid exponential execution:
            if pos in self.failures:
                return None
    
            results = []
    
            # The entire source may be contained inside the dictionary:
            if source in self.dictionary:
                results.append([source])
    
            # Max word size:
            size = min(len(source) - 1, self.dictionaryMaxLen)  # Leaves at least one character for the tail.
    
            # Tries with part of the source, first with longer ones:
            while size > 0:
    
                # Splits the source into two parts, head and tail:
                head, tail = source[:size], source[size:]
    
                # If head is not in the dictionary skips current case:
                if head not in self.dictionary:
                    size -= 1
                    continue
    
                # Continues with the tail:
                tailResults = self._wordBreak(tail, pos + size)
                if not tailResults:
                    size -= 1
                    continue  # No solutions, skips current case.
    
                # Collects the results after prepending the head to them:
                for result in tailResults:
                    result.insert(0, head)
                    results.append(result)
    
                # Tries with smaller words:
                size -= 1
    
            # On failure, memoizes it:
            if len(results) == 0:
                self.failures.add(pos)
                return
    
            return results
    

Log in to reply
 

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