力扣hot100 单词拆分 变形背包 排列

Problem: 139. 单词拆分

思路

👨?🏫 参考题解

复杂度

时间复杂度: $O(n^3)$

💖 Code

class Solution {
	public boolean wordBreak(String s, List<String> wordDict)
	{
		Set<String> set = new HashSet<>(wordDict);
		boolean[] f = new boolean[s.length() + 1];
		Arrays.fill(f, false);
		f[0] = true;
		for (int i = 1; i <= s.length(); i++)//枚举背包容量
			for (int j = 0; j < i && !f[i]; j++)//枚举物品
				if (set.contains(s.substring(j, i)) && f[j])
					f[i] = true;
		return f[s.length()];
	}
}