LintCode 683 Word Break III

LintCode 683 Word Break III

Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example 1:

Input:
“CatMat”
[“Cat”, “Mat”, “Ca”, “tM”, “at”, “C”, “Dog”, “og”, “Do”]
Output: 3
Explanation:
we can form 3 sentences, as follows:
“CatMat” = “Cat” + “Mat”
“CatMat” = “Ca” + “tM” + “at”
“CatMat” = “C” + “at” + “Mat”

Example 2:

Input:
“a”
[]
Output: 0

题目大意：

一个字符串s，被“字典集合”（wordDict）中的单词拼接而成的可能性种数。

解题思路：

这是经典题。如果知道s[0:n-1)很容易知道s[0:n)是否有解，既然和子问题有关，就用DP。

1. 定义dp[i]为字符串s[0,i)是合法分解种数。
2. 判断一个字符串是否可以合法分解，方案是尝试在每一位进行分解，若其中一个可分解，即有解，加入到dp[i]中。
   递归式为dp[i] += dp[k] * isWord(s[k:i)), 0 <= k < i.
3. 方向为从左到右i=0..n, 初始值为dp[0] = 1.

注意事项：

1. 将两个输入都转换成小写。
2. dp[n+1]而不是dp[n]，而for循环从1开始。
3. 递归中dp[i]用+操作符。

Java代码：

public int wordBreak3(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	Set<String> lowerDict = new HashSet<>();
	for(String c : dict)
		lowerDict.add(c.toLowerCase());
	dict = lowerDict;
	s = s.toLowerCase();
	
	int[] dp = new int[s.length() + 1];
	dp[0] = 1;
	
	// dp[i][j] = sum(dp[i][k] * isWord(s[k,j])), i=0..n-1, j=i..n-1
	// dp[0][n-1] = sum(dp[0][k] * isWord(s[k,n-1]))
	// dp[n] = sum(dp[k] * isWord(s[k,n]))
	for(int i = 1; i <= s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k, i)) ? 1 : 0); 
		}
	}
	return dp[s.length()];
}

算法分析：

时间复杂度为O(n2)，空间复杂度为O(n)。

这道题一开始走过一些弯路，首先我觉得类似于Catalan算法，左右半部都是子问题，但其实这属于单边问题。所以写了以下算法：

Java代码：

public int wordBreak3_wrong(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	// dp[i][j] = sum(dp[i][k] * dp[k][j])
	int[][] dp = new int[s.length() + 1][s.length() + 1];
	
	// use "ab" as an example
	for(int len = 1; len <= s.length(); len++) {
		for(int i = 0; i < s.length() - len + 1; i++) {
			for(int j = i + 1; j < i + len; j++) {
				//"a","b"
				dp[i][i+len] += dp[i][j] * dp[j][i+len];    		
			}
			//"ab"
			if(dict.contains(s.substring(i, i+len)))
				dp[i][i+len]++;
			
		}
	}
	return dp[0][s.length()];
}

但这个方法会有重复解，比如
“abc”, “a”,”b”,”c”
-> dp["ab"] * dp["c"] = 1
-> dp["a"] * dp["bc"] = 1
所以解重复，因为这问题是单边子问题而不是Catalan问题。
更改版本为单边子问题，一开始用dp[n]导致初始化稍复杂，其实初始化可以并入到递归式，只要用dp[n+1]即可。

Java代码：

public int wordBreak32(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	int[] dp = new int[s.length()];
	for(int i = 0; i < s.length(); i++)
		dp[i] = dict.contains(s.substring(0, i + 1)) ? 1 : 0;

	for(int i = 0; i < s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k + 1, i + 1)) ? 1 : 0); 
		}
	}
	return dp[s.length() - 1];
}