leetcode 139. Word Break | 139. 单词拆分（动态规划）

题目

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

题解

时隔一天，再次遇到 dp 问题…
本题和 leetcode 375. Guess Number Higher or Lower II | 375. 猜数字大小 II（动态规划思路总结）的思路是一样的，连 dp 数组的遍历方向都是一样的（斜向）…
这是全局第 5 道没看答案的 dp 问题，所以，dp 到底是不是玄学？…

以下面的测试用例为例，斜向依次填充 dp 数组过程如图所示。

public static void main(String[] args) {Solution solution = new Solution();List<String> list = new ArrayList<>();list.add("cat");list.add("cats");list.add("and");list.add("sand");list.add("dog");list.add("catsanddog");solution.wordBreak("catsanddog", list); }

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> dict = new HashSet<>();for (String word : wordDict) {dict.add(word);}int n = s.length();boolean[][] dp = new boolean[n + 1][n + 1];for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {int L = j - i;int R = j;if (dict.contains(s.substring(L, R))) {dp[L][R] = true;} else {for (int M = L + 1; M < R; M++) {// [L...M) + [M...R)if (dp[L][M] & dp[M][R]) {dp[L][R] = true;break;}}}}}return dp[0][n];} }

总结

以上是生活随笔为你收集整理的leetcode 139. Word Break | 139. 单词拆分（动态规划）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。