Does my very simple pythonic code using an algorithm?


  • 0
    C

    Hi,

    I have not much knowledge about algorithm, but I have written many real project using python for years. So I resolve this problem in a simple pythonic way instead the complicated algorithm way, nothing too magic.

    My question is, does my code using any algorithm?

    import functools
    
    
    def memoize(obj):
        cache = obj.cache = {}
     
        @functools.wraps(obj)
        def memoizer(*args, **kwargs):
            if args not in cache:
                cache[args] = obj(*args, **kwargs)
            return cache[args]
        return memoizer
     
     
    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a list of strings
        def wordBreak(self, s, dict):
     
            # lazy way for the cache decorator
            @memoize
            def _wordBreak(s):
                # print(s)
                results = []
                for word in dict:
                    if s == word:
                        results.append(word)
                    elif s.startswith(word):
                        # print('got', word)
                        for result in _wordBreak(s[len(word):]):
                            results.append(word+' '+result)
     
                return results
     
            return _wordBreak(s)

  • 2
    R

    You just used DP (dynamic programming) to memoize in a cache the recursions that have already been executed.

    I have to study such cool python feature ;-)


  • -1
    R

    A solution similar to your, but with a more conservative approach (no decorators), also uses DP to memoize solutions:

    class Dictionary:
        
        def __init__(self, dictionary):
            self._dictionary = dictionary
            self._cache = dict()
    
        def wordBreak(self, text):
            
            # If cached takes it from the cache:
            if text in self._cache:
                return self._cache[text]
            
            # Generates the result recursively:
            results = list()
            for word in self._dictionary:
                if word == text:
                    results.append(word)
                elif text.startswith(word):
                    for result in self.wordBreak(text[len(word):]):
                        results.append(word + " " + result)
                        
            # Memoizes the result:
            self._cache[text] = results
            return results
    
    
    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a list of strings
        def wordBreak(self, s, dict):
            return Dictionary(dict).wordBreak(s)

  • 0
    C

    Thank you =)


Log in to reply
 

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