WordBreak2
题目地址：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. You may assume the dictionary does not contain duplicate words. Return all such possible sentences. For example, given s = "catsanddog" , dict = ["cat", "cats", "and", "sand", "dog"] . A solution is ["cats and dog", "cat sand dog"] . 思路： 解决此题的关键在于用dfs来返回从某个起点开始的所有可行的解；用map是为了来memorize之前算过的解，可以大幅度减少运行时间；另外还有一些小技巧比如maxLen的使用来节省时间等。红色标记部分是memorization。 代码： Map <Integer, List<String>> map = new HashMap<>(); public List<String> wordBreak(String s, List<String> wordDict) { List<String> rst = new ArrayList<>(); if (s == null || s.length() == 0 ){ return rst; } int maxLen = - ...