LeetCode: Word Break II [140]

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

s = <code>"catsanddog"</code>,

dict = <code>["cat", "cats", "and", "sand", "dog"]</code>.

A solution is <code>["cats and dog", "cat sand dog"]</code>.

    給定一個字元串s和詞典dict, 傳回全部切分情況。使得切分後每一個單詞都是dict中的單詞

        依次确定以每一個位置i結尾的單詞的前驅單詞集合（僅僅要記住前驅單詞的結束位置）

        然後從後往前恢複切分路徑就可以。

        DP問題

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5354673.html，如需轉載請自行聯系原作者