# Does my very simple pythonic code using an algorithm?

• 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)``````

• 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 ;-)

• 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)``````

• Thank you =)

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