LeetCode | Word Break II

題目

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

直接的思路就是用動態規劃，實現中要注意：

1. 需要加上備忘錄，避免超時；

2. 需要判斷句子是否能正確分割，下述代碼中，利用null來標識不能分割的子句；

3. 下述代碼中，沒有在意空間，備忘錄中直接紀錄了各個子句的字符串分割結果；如果空間上有所限制的話，可以在備忘錄中紀錄分割點的索引，最後再生成結果；

4. 進一步提升性能的話，可以左右同時開工，建立二維的備忘錄。

代碼

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class WordBreakII {
	private Map> records = new HashMap>();
	private Set dict = null;
	private String s = null;
	private int N = 0;

	public ArrayList wordBreak(String s, Set dict) {
		// Note: The Solution object is instantiated only once and is reused by
		// each test case.
		if (s == null || s.length() <= 0 || dict == null || dict.size() <= 0) {
			return new ArrayList();
		}
		records.clear();
		this.dict = dict;
		this.s = s;
		N = s.length();

		ArrayList list = solve(0);
		if (list == null) {
			list = new ArrayList();
		}
		return list;
	}

	private ArrayList solve(int i) {
		if (records.containsKey(i)) {
			return records.get(i);
		}

		ArrayList list = new ArrayList();
		if (i >= N) {
			records.put(i, list);
			return list;
		}
		for (int j = i + 1; j <= N; ++j) {
			String word = s.substring(i, j);
			if (dict.contains(word)) {
				ArrayList subList = solve(j);
				ArrayList newList = new ArrayList();
				if (subList == null) {
					continue;
				} else if (subList.size() == 0) {
					newList.add(word);
				} else {
					for (String result : subList) {
						newList.add(word + " " + result);
					}
				}
				list.addAll(newList);
			}
		}
		if (list.size() == 0) {
			list = null;
		}
		records.put(i, list);
		return list;
	}
}