Word break problem with recursion and memorization For practice, I solved Leetcode 139. worbreak question:


  Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.


I have the solution to use the recursive with in-memory hash table to reduced to duplication calculation. but it seems like works for some case but not all. any suggestions?

def wordbreak(self, s, wordDict):
    wordDict = set(wordDict)
    str_map = dict()
    if not s or not wordDict: return False

    def check(s):
        if s in str_map: return str_map[s]
        if s in wordDict:
            str_map[s] = True
            return True
        for i, c in enumerate(s[1:], 1):
            if s[:i] in set(wordDict) and check(s[i:]):
                str_map[s[:i]] = True
        str_map[s] = False
        return False

    return check(s)


if __name__ == '__main__':
    testcase = [
        dict(tc=dict(s='ab', wordDict=['a', 'b']), exp=True),
        dict(tc=dict(s='leetcode', wordDict=['leet', 'code']), exp=True),
        dict(tc=dict(
            s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
            wordDict=["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa",
                      "aaaaaaaaaa"]), exp=False),
    ]
    for tc in testcase:
        res = wordbreak(**tc['tc'])
        print(res) # True, True, False
bug

def wordBreak(self, s, wordDict):
    wordDict = set(wordDict)
    str_map = dict()
    if not s or not wordDict: return False

    def check(s):
        if s in str_map: return str_map[s]
        if s in wordDict:
            str_map[s] = True
            return True
        for i, c in enumerate(s[1:], 1):
            if s[:i] in set(wordDict) and check(s[i:]):
                str_map[s[:i]] = True
                return True  # &lt;== you forgot this one
        str_map[s] = False
        return False

    return check(s)


passes all cases in 48ms

set(wordDict)

No need to do this in each iteration if you do that at the start of the algorithm

c

this variable is not used. Python convention uses _ for variables that are not used

reinventing the wheel (cache)

Python is batteries included

so you can as easily use functools.lru_cache instead of implementing your own cache:

from functools import lru_cache

def wordBreak(self, s, wordDict):
    wordDict = set(wordDict)
    if not s or not wordDict: return False
    @lru_cache(None)
    def check(s):
        if s in wordDict:
            return True
        for i, _ in enumerate(s[1:], 1):
            if s[:i] in wordDict and check(s[i:]):
                return True
        return False
    return check(s)


passes in 36ms



alternative version

instead of running over the string, you can also try to build a graph of all occurrences of the words in wordDict, and then look if you can find a path from 0 to len(s)

all chars in wordDict

you can check whether all chars in s appear in a word in wordDict

def validate_all_chars(text, words):
    all_chars = set()
    for word in words:
        all_chars.update(word)
    return all_chars.issuperset(text)


or with itertools.chain:

from itertools import chain
def validate_all_chars(text, words):
    all_chars = set(chain.from_iterable(words))
    return all_chars.issuperset(text)


occurrences:

Unfortunately, re.finditer and re.findall only give non-overlapping occurrences, so we can't use them here. So we'll have to build our own finder:

def find_occurrences(pattern: str, text: str):
    idx = 0
    while True:
        idx = text.find(pattern, idx)
        if idx == -1:
            return
        yield idx, idx + len(pattern)
        idx += 1


build a graph

from collections import defaultdict
def build_span_graph(text, words):
    all_spans = defaultdict(set)
    spans = (find_occurrences(word, text) for word in words)
    for span in spans:
        for begin, end in span:
            all_spans[begin].add(end)
    return all_spans


walk the graph:

def find_path(spans, length, begin=0, visited=None):
    visited = set() if visited is None else visited
    visited.add(begin)
    ends = spans[begin]
    return length in ends or any(
        find_path(spans, length=length, begin=new_begin, visited=visited)
        for new_begin in ends
        if new_begin not in visited and new_begin in spans
    )


Here you can try to optimize a bit by first visiting the furthest ends, but that is only marginally useful

main:

def wordBreak(s: "str", wordDict: "List[str]") -&gt; "bool":
    if not validate_all_chars(s, wordDict):
        return False

    spans = build_span_graph(s, wordDict)

    return find_path(s, wordDict)