[LeetCode]Word Break

boolean数组arr记录前k个字母是否在字典里，每次扫第i位时候，把arr从i到0扫一遍，看前j个和从j到i组成的substring是不是在字典里，有一组在的话说明前i + 1个可以break，没有的话就说明不行，时间复杂度O(N^2)。用f[i]代表能不能break，DP方程：

• f[i] = (f[i] && dict.contains(s.substring(i, i + 1))) || (f[i - 1] && dict.contains(s.substring(i - 1, i + 1))) ||......|| (f[0] && dict.contains(s.substring(0, i + 1)))

代码如下：

	public class Solution {
	public boolean wordBreak(String s, Set<String> dict) {
	if (s == null || dict == null)
	return false;
	int len = s.length();
	boolean[] arr = new boolean[len + 1];
	arr[0] = true;
	for (int i = 0; i < len; i++) {
	boolean isBreak = false;
	for (int j = i; j >= 0; j--) {
	isBreak = arr[j] && dict.contains(s.substring(j, i + 1));
	if (isBreak)
	break;
	}
	arr[i + 1] = isBreak;
	}
	return arr[len];
	}
	}

view raw word break.java hosted with ❤ by GitHub