首页 > 代码库 > Word Break II 求把字符串拆分为字典里的单词的所有方案 @LeetCode
Word Break II 求把字符串拆分为字典里的单词的所有方案 @LeetCode
这道题类似 Word Break 判断是否能把字符串拆分为字典里的单词 @LeetCode 只不过要求计算的并不仅仅是是否能拆分,而是要求出所有的拆分方案。因此用递归。
但是直接递归做会超时,原因是LeetCode里有几个很长但是无法拆分的情况,所以就先跑一遍Word Break,先判断能否拆分,然后再进行拆分。
递归思路就是,逐一尝试字典里的每一个单词,看看哪一个单词和S的开头部分匹配,如果匹配则递归处理S的除了开头部分,直到S为空,说明可以匹配。
public class Solution { public List<String> wordBreak(String s, Set<String> dict) { List<String> list = new ArrayList<String>(); List<String> ret = new ArrayList<String>(); rec(s, dict, list, ret); return ret; } public void rec(String s, Set<String> dict, List<String> list, List<String> ret) { if(!isBreak(s, dict)){ // test before run to avoid TLE return; } if(s.length() == 0) { String concat = ""; for(int i=0; i<list.size(); i++) { concat += list.get(i); if(i != list.size()-1) { concat += " "; } } ret.add(concat); return; } for(String cur : dict) { if(cur.length() > s.length()) { // avoid out of boundary continue; } String substr = s.substring(0, cur.length()); if(substr.equals(cur)) { list.add(substr); rec(s.substring(cur.length()), dict, list, ret); list.remove(list.size()-1); } } } public boolean isBreak(String s, Set<String> dict) { boolean[] canBreak = new boolean[s.length()+1]; canBreak[0] = true; for(int i=1; i<=s.length(); i++) { boolean flag = false; for(int j=0; j<i; j++) { if(canBreak[j] && dict.contains(s.substring(j,i))) { flag = true; break; } } canBreak[i] = flag; } return canBreak[s.length()]; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。