跟word break 相比,该题需要输入具体的方案
步骤如下
1. 使用map,存储第k个位置之前的字符串,所有的单词划分方案
2. 修剪分支,将一些不符合完全划分的单词除去
3. 遍历,获得所有符合条件的方案
public class Solution { public List<String> wordBreak(String s, Set<String> dict) { Map<Integer, List<Integer>> pMapALL = new HashMap<Integer, List<Integer>>(); boolean[] f = new boolean[s.length()]; for (int i = 0; i < s.length(); i++) { boolean flag = false; if (dict.contains(s.substring(0, i + 1))) { put(pMapALL, i, -1); flag = true; } for (int j = 0; j < i; j++) { if (f[j] && dict.contains(s.substring(j + 1, i + 1))) { put(pMapALL, i, j); flag = true; } } if (flag) { f[i] = true; } } if (f[s.length() - 1]) { Map<Integer, List<Integer>> pMap = new HashMap<Integer, List<Integer>>(); LinkedList<Integer> stack = new LinkedList<Integer>(); stack.push(s.length()-1); while (!stack.isEmpty()){ Integer node = stack.pop(); List<Integer> children = pMapALL.get(node); if(children != null){ pMap.put(node, children); for(Integer child : children){ stack.push(child); } } } List<String> results = new ArrayList<String>(); for(Integer key : pMap.keySet()){ List<Integer> children = pMap.get(key); if(children.contains(-1)){ print(pMap, -1, key, s, new LinkedList<String>(), results); } } return results; } return new ArrayList<String>(); } private void put(Map<Integer, List<Integer>> pMap, Integer key, Integer value) { if (pMap.get(key) == null) { pMap.put(key, new ArrayList<Integer>()); } pMap.get(key).add(value); } private void print(Map<Integer, List<Integer>> pMap, Integer startIndex, Integer endIndex, String s, LinkedList<String> stack, List<String> results) { String word = s.substring(startIndex+1, endIndex+1); stack.push(word); if(endIndex == s.length()-1){ StringBuilder words = new StringBuilder(); for(int i=stack.size()-1; i>=0; i--){ words.append(stack.get(i)); if(i != 0){ words.append(" "); } } results.add(words.toString()); return; } for(Integer key : pMap.keySet()){ List<Integer> children = pMap.get(key); for(Integer child : children){ if(child.equals(endIndex)){ print(pMap, child, key, s, stack, results); stack.pop(); } } } } }
相关推荐
Article-Views-II-LeetCode.png 平均工资-部门-VS-公司-LeetCode.png 平均销售价格-LeetCode.png 每台机器平均处理时间 LeetCode.png Bank-Account-Summary-II-LeetCode.png Bank-Account-Summary-LeetCode.png 大国...
leetcode 答案Leetcode-Java - 符合条件(Hacktoberfest) JAVA 中的 Leetcode 答案
leetcode 跳跃 LeetCode-Java 缺失的第一个正数 接雨水 跳跃游戏 II
LeetCode-Java 说明 leetcode练习,坚持每天一道,目前已完成275道 解题语言是Java 每道题都是可编译运行的 每道题有自己的方法和他人优秀解法 每道题会尽量分析一下解题步骤和复杂度 欢迎star、fork、交流,一起...
leetcode题库 leetcode-java 用Java实现leetcode题库
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
leetcode 答案 leetcode-java 记录Leetcode之旅。 内容包括最终的答案,思考和截图等。 一道题可能会在一段时间之内复习,所以会有不同的答案。
java lru leetcode leetcode-algorithms-java leetcode 算法笔记-java
leetcode-java LeetCode Java Solution 题目 : : : : more : : : : : : more : : : 题解 recursion 104题解 解法:递归 复杂度:O(n)、O(h) class Solution { public int maxDepth(TreeNode root) { //...
分类LeetCode-Java-接受 这是 Leetcode 问题的 Java 解决方案。 细节 标题和答案格式 /* * 17. Letter Combinations of a Phone Number * Target: Given a string containing digits from 2-9 inclusive, return all...
本仓库内包含了java实现的leetcode解法,代码规范,可读性良好,其中的解法思想并不受语言限制。 BFS(Breath First Search) bfs能解决什么样的问题 图遍历中是否可达、最短路径等等。 普通bfs解题框架 一个boolean[]...
Java Linked List Linked List Cycle Given a linked list, determine if it has a cycle in it. public static boolean hasCycle(ListNode head) 快慢指针法,块指针从head.next开始,慢指针从head开始,快指针每次...
awesome-java-leetcode 我如今是一名 Android Developer,大学的我曾是一名 ACMer,我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的,为了不让数据结构和算法淡出我的记忆,所以我打算重拾 LeetCode ...
java lru leetcode LeetCode-Tag-Java 解决方案 LeetCode 的解决方案 指数
解压Leetcode-Solution-With-Java 用 Java 8 解决 Leetcode 问题 编号 问题 解决方案 困难 01 简单的 02 中等的 03 无重复字符的最长子串 中等的 04 两个有序数组的中位数 难的 653 二和 IV - 输入是 BST 简单的 ...
java lru leetcode Java 中的 Leetcode 解决方案 算法 # 问题 解决方案 1 [Java](/Java/001 二和.java) 2 [Java](/Java/002 加两个数.java) 3 [Java](/Java/003 无重复字符最长子串.java) 4 [Java](/Java/004 两个...
这个库文件中的所有代码均由java语言编写,所有题目皆来自于LeetCode官网 关于这些代码,有以下几点说明: 1.所有代码均为原创,可随意转载、使用、修改; 2.代码以简洁明了为原则,逻辑清晰; 3.欢迎大家随时交流,...
leetcode-java leetcode题库Java解决方案 这是一个IntelliJ IDEA项目,请安装IntelliJ IDEA Test.java是测试入口,如要测试请修改Q后面的数字,比如这是测试第23题 public static void main(String[] args) { ...
答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II Remove ...
LeetCode题解 - Java语言实现-181页.pdf