140. Word Break II.md

140. Word Break II

Problem

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 = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

tag:

• backtracking
• dp
• 记忆化搜索

Solution

直接DFS， 会TLE :(

采用记忆化搜索进行剪枝：在搜索的过程中，用map纪录已经搜索过的结果

java

	public List<String> wordBreak(String s, Set<String> wordDict) {
		return memSearch(s, wordDict, new HashMap<String, LinkedList<String>>());
	}

	List<String> memSearch(String s, Set<String> dict, HashMap<String, LinkedList<String>> map) {
		if (map.containsKey(s))
			return map.get(s);
		LinkedList<String> res = new LinkedList<String>();
		if (s.length() == 0) {
			res.add("");
			return res;
		}
		for (String word : dict) {
			if (s.startsWith(word)) {
				List<String> subList = memSearch(s.substring(word.length()), dict, map);
				for (String sub : subList)
					res.add(word + (sub.isEmpty() ? "" : " ") + sub);
			}
		}
		map.put(s, res);
		return res;
	}

go