Two versions of Word Break II - exhaustive combinations

Question

I am solving Word Break II from leetcode:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Input:

s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output:

[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]

Explanation: Note that you are allowed to reuse a dictionary word.

I think my Python has improved since I posted island problem last. Your input is appreciated.

Here are the two solutions:

def inverse_iterative(s, wdict):
    st = []
    ans = []

    for w in wdict:
        if s.startswith(w):
            if len(s) == len(w):
                ans.append(w)
                return ans
            st.append((w, 0, [w]))

    while st:
        cur_w, cur_idx, cur_list = st.pop()
        cur_start = cur_idx + len(cur_w)


        for w in wdict:
            if not s[cur_start:].startswith(w):
                continue
            if len(w) == len(s[cur_start:]):
                ans.append(' '.join(cur_list+[w]))
            else:
                st.append((w, cur_start, cur_list+[w]))
    return ans

def inverse_helper(s, wdict, memo):
    if s in memo:
        return memo[s]
    if not s:
        return []

    res = []
    for word in wdict:
        if not s.startswith(word):
            continue
        if len(word) == len(s):
            res.append(word)
        else:
            result_of_rest = helper(s[len(word):], wordDict, memo)
            for r in result_of_rest:
                r = word + ' ' + r
                res.append(r)

    memo[s] = res
    return res

ans_iterative = inverse_iterative(s, wdict) 
ans_recursive = inverse_helper(s, wdict, {})

Answer 1

The first solution

There's a bug in the first loop:

    for w in wdict:
        if s.startswith(w):
            if len(s) == len(w):
                ans.append(w)
                return ans
                ^^^^^^^^^^ should not do this!
            st.append((w, 0, [w]))

It's not correct to return when one of the words is the same as the sentence, because there might be other words to compose that sentence. At it is, the program produces incorrect result for the input:

"foobar"
["foobar", "foo", "bar"]

---

The first loop duplicates some of the logic of the second loop. You can remove the first loop completely if you initialize st like this:

st = [('', 0, [])]

---

This solution is much slower than the second, because unlike the second, it doesn't do anything to avoid repeated computation of sub-problems. For example, if the input string is "foobar" + some_very_long_string, and the word list has "foo", "bar", and "foobar", then the sentences for some_very_long_string will be computed twice at least, for the "foo bar" and "foobar" prefixes.

The second solution

The posted code is broken, probably you copy-pasted a work-in-progress version:

result_of_rest = helper(s[len(word):], wordDict, memo)

This line references the nonexistent function helper, and the nonexistent variable wordDict. The fix is easy enough:

result_of_rest = inverse_helper(s[len(word):], wdict, memo)

Next time please make sure to post working, verified code!

---

This solution implements memoization manually. Python has a cool technique to make this easier, using lru_cache from the functools package. In a nutshell, all you need is a function with hashable arguments, and then you can simply annotate it with @lru_cache to benefit from easy memoization.

from functools import lru_cache


def word_break_helper(text, wdict):
    @lru_cache(maxsize=128)
    def helper(s):
        res = []
        for word in wdict:
            if not s.startswith(word):
                continue
            if len(word) == len(s):
                res.append(word)
            else:
                for sentence in helper(s[len(word):]):
                    res.append(word + ' ' + sentence)
        return res

    return helper(text)

Use better names

The names used in both solutions are quite poor.

I don't know what's "inverse" about these solutions. Sure, the first one uses a stack, to which it appends and pops values, but it's not really important anyway. So I don't get "inverse" in these names.

res, and ans are poor as well. Why not naturally sentences?

wordDict doesn't follow Python naming conventions (should be snake_case).

Further improving performance

Although it doesn't seem to be important in this puzzle, looping over the list of supported words to find possible prefixes would be inefficient with a large number of words. You could use a more efficient data structure to retrieve potential prefix words without iterating over all the supported words.