139. 单词拆分

问题139 单词拆分 ★★★☆☆

https://leetcode-cn.com/problems/word-break/

这个题目并不难想到使用动态规划，关键是状态转移方程。我们定义dp[i]表示字符串s的前i个字符对应的子串是否满足wordBreak，那么怎么得到dp[i+1]呢？如果dp[i]是true并且wordDict包含s[i, i+1]，那么dp[i+1]为true，或者如果dp[i-1]是true并且wordDict包含s[i-1, i+1]，那么dp[i+1]为true，或者如果dp[i-2]是true并且wordDict包含s[i-2, i+1]，那么dp[i+1]为true，……，或者如果dp[0]是true并且wordDict包含s[0, i+1]，那么dp[i+1]为true.

	public boolean wordBreak(String s, List<String> wordDict) {
		int length = s.length();

		boolean[] dp = new boolean[length + 1]; // dp[i] represents whether s[0..i-1] fits wordBreak
		dp[0] = true;

		for (int i = 1; i <= length; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (dp[j] && wordDict.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}

		return dp[length];
	}

在 LeetCode 查看