1
\$\begingroup\$

I am solving Word Break II from leetcode.

https://leetcode.com/problems/word-break-ii/description/

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, {})
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.