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

题目

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

题解

由 leetcode 139. Word Break | 139. 单词拆分（动态规划） 改造而来。

dp 过程示例:

class Solution {public List<String> wordBreak(String s, List<String> wordDict) {HashSet<String> dict = new HashSet<>();for (String word : wordDict) {dict.add(word);}int n = s.length();ArrayList<int[]>[][] dp = new ArrayList[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;dp[L][R] = new ArrayList<>();if (dict.contains(s.substring(L, R))) {ArrayList<int[]> t = new ArrayList<>();t.add(new int[]{L, R});dp[L][R] = t;}for (int M = L + 1; M < R; M++) {// [L...M) + [M...R)if (dp[L][M] != null && dp[L][M].size() > 0 && dp[M][R] != null && dp[M][R].size() > 0) {dp[L][R].add(new int[]{L, M});dp[L][R].add(new int[]{M, R});}}}}Set<String> res = join(dp, 0, n, s);return new ArrayList<>(res);}public Set<String> join(ArrayList<int[]>[][] dp, int L, int R, String s) {ArrayList<int[]> pair = dp[L][R];Set<String> res = new HashSet<>();int i = 0;if (pair.size() % 2 == 1) {res.add(s.substring(L, R));i = 1;}for (; i + 1 < pair.size(); i += 2) {Set<String> lSet = join(dp, L, pair.get(i)[1], s);Set<String> rSet = join(dp, pair.get(i + 1)[0], R, s);for (String l : lSet) {for (String r : rSet) {res.add(l + " " + r);}}}return res;} }

总结

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

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