Куда вставить памятку в итерационной версии? - PullRequest
Новая
       29

Куда вставить памятку в итерационной версии?

0 голосов
/ 12 октября 2018

Я решаю Word Break II из кода leetcode.

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

Учитывая непустую строку s и словарь wordDict, содержащий список непустых слов, добавьте пробелы в s, чтобы создать предложение, где каждое слово являетсядопустимое словарное слово.Возвратите все такие возможные предложения.

Примечание:

Одно и то же слово в словаре может многократно использоваться в сегментации.Вы можете предположить, что словарь не содержит повторяющихся слов. 

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.

Я получил рекурсивное решение, но я борюсь с итерационным решением.В основном, решение верное, но у leetcode есть патологический случай, и он не запустится без запоминания.Я передал практику leetcode с рекурсивной версией, но я не мог отпустить итеративное решение.Но я не могу найти хорошее место, чтобы сделать памятку.Ваши предложения приветствуются.

Вот два решения: 

   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
...