单词拆分-动态规划-LeetCode

问题描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。

示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2： 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。

示例 3： 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

解题思路

代码实现

package solution; import java.util.*; class Solution { List<List<String>> lists; public static void main(String[] args) { List<String> list=new ArrayList<>(); list.add("cats"); list.add("dog"); list.add("sand"); list.add("and"); list.add("cat"); new Solution().wordBreak("catsandog",list); } public boolean wordBreak(String s, List<String> wordDict) { if (s == null || s.length() == 0) { return true; } Set<String> set = new HashSet<>(wordDict); int maxLen = getMaxLen(set); // 长度为n的单词一共有n + 1个切点 boolean[] canSegment = new boolean[s.length() + 1]; canSegment[0] = true; for (int i = 1; i < canSegment.length; i ++) { for (int j = 1; j <= maxLen && j <= i; j ++) { // i - j 表示从i往前j个位置 String str = s.substring(i - j, i); //如果单词符合条件并且这个单词的第一个字母对应的canSegment已经是true if (set.contains(str) && canSegment[i - j]) { canSegment[i] = true; break; } } } return canSegment[canSegment.length - 1]; } private int getMaxLen(Set<String> set) { int maxLen = 0; for (String word : set) { maxLen = Math.max(maxLen, word.length()); } return maxLen; } }

单词拆分2

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] 输出: [ "cats and dog", "cat sand dog" ]

示例 2：

输入: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] 解释: 注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: [] package solution; import java.util.ArrayList; import java.util.List; public class Solution4 { public static void main(String[] args) { String s="catsanddog"; List<String> wordDict = new ArrayList<>(); wordDict.add("cat"); wordDict.add("cats"); wordDict.add("dog"); wordDict.add("sand"); wordDict.add("and"); new Solution4().wordBreak(s,wordDict); System.out.println(s); } private List<String> result; public List<String> wordBreak(String s, List<String> wordDict) { if (wordDict.size()<1){ return new ArrayList<>(); } result=new ArrayList<>(); //先判断是否可以拆分 if(!confirm(s,wordDict)){ return result; } //每次遍历拆分的标记 boolean[] flag=new boolean[s.length()]; //如果可以拆分 find(s,0,flag,wordDict); return result; } private boolean confirm(String s,List<String> words){ boolean[] flag=new boolean[s.length()+1]; flag[0]=true; //找到字典中最长的单词长度 int maxLen=findMax(words); for(int i=1;i<flag.length;i++){ //查看i之前的单词是否满足，单词的最大长度为maxLen for(int j=1;j<=maxLen&&j<=i;j++) { String str=s.substring(i-j,i); //str的第一个字母对应的标记已经为true，并且str在字典内 if(flag[i-j]&&words.contains(str)){ flag[i]=true; } } } return flag[flag.length-1]; } private int findMax(List<String> words) { int max=words.get(0).length(); for(String s:words){ if(max<s.length()){ max=s.length(); } } return max; } private void find(String s,int index,boolean[] flag,List<String> words){ //标记完毕，开始分割 if(index==s.length()){ StringBuilder sb=new StringBuilder(); int begin=0;//分割起始点 for(int last=0;last<s.length();last++){ if(flag[last]){ sb.append(s.substring(begin,last+1)+" "); begin=last+1; } } sb.deleteCharAt(sb.length()-1); result.add(sb.toString()); } for(int i=index;i<s.length();i++){ //从index开始标记满足条件的单词 if(words.contains(s.substring(index,i+1))){ flag[i]=true; //满足条件，再从i+1开始标记 find(s,i+1,flag,words); //一轮遍历完后，将所有标记清除 flag[i]=false; } } } }