现在的位置: 首页 > 综合 > 正文

[LeetCode] Word Break II

2014年01月27日 ⁄ 综合 ⁄ 共 1500字 ⁄ 字号 评论关闭

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

这题跟Word Break I一样,简单的使用递归会超时。结合前一题的解法做剪枝,只对能够被拆解的子字符串进行后续DFS,这样可以有效减少DFS的搜索空间。

可以直接照搬前一版本的代码。

	// do DFS only if seg[start][len] is true
	private void dfs(String s, boolean seg[][], int start,
			ArrayList<String> ret, StringBuilder sb, Set<String> dict) {
		// exit
		if ("".equals(s)) {
			// need to trim the ending white space
			ret.add(sb.substring(0, sb.length() - 1));
		}

		for (int len = 1; len <= s.length(); len++) {
			// do pruning here
			if (seg[start][len]) {
				String str = s.substring(0, len);
				if (dict.contains(str)) {
					sb.append(str).append(" ");
					dfs(s.substring(len), seg, start + len, ret, sb, dict);
					// backtrack
					sb.delete(sb.length() - str.length() - 1, sb.length());
				}
			}
		}
	}

	public ArrayList<String> wordBreak(String s, Set<String> dict) {
		ArrayList<String> ret = new ArrayList<String>();
		// directly use the code of word break I here for later pruning flag
		if ("".equals(s))
			return ret;
		// seg[i][0] is wasted
		boolean seg[][] = new boolean[s.length()][s.length() + 1];
		for (int len = 1; len <= s.length(); len++) {
			for (int i = 0; i < s.length(); i++) {
				if (i + len <= s.length()) {
					// 1) seg(i, len) is a dictionary word
					if (dict.contains(s.substring(i, i + len))) {
						seg[i][len] = true;
						continue;
					}
					// 2) seg(i, k) and seg(i + k, len - k) can be segmented
					for (int k = 1; k < len; k++) {
						if (seg[i][k] && seg[i + k][len - k]) {
							seg[i][len] = true;
							break;
						}
					}
				}
			}
		}

		// if no solution
		if (!seg[0][s.length()])
			return ret;

		dfs(s, seg, 0, ret, new StringBuilder(), dict);

		return ret;
	}

抱歉!评论已关闭.