leetCode: Word Break I & Word Break II

左手的ㄟ右手 2022-08-26 01:00 111阅读 0赞

**题目：**

## Word Break ##

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given  
s = `"leetcode"`,  
dict = `["leet", "code"]`.

Return true because `"leetcode"` can be segmented as `"leet code"`.

**分析：**

一开始看到这个题目，我的第一反应是要递归，但是之后感觉递归的做法估计没办法通过，然后就开始想，之后看到别人的思路之后，感觉其实还挺容易的。

**解题思路：**

一个字符串S，它的长度为N，如果S能够被“字典集合”（dict）中的单词拼接而成，那么所要满足的条件为：

**F(0, N) = F(0, i) && F(i, j) && F(j, N);**

这样子，如果我们想知道某个子串是否可由Dict中的几个单词拼接而成就可以用这样的方式得到结果（满足条件为True, 不满足条件为False）存入到一个boolean数组的对应位置上，这样子，最后boolean数组的最后一位就是F(0, N)的值，为True表示这个字符串S可由Dict中的单词拼接，否则不行！

话不多说，上AC代码！！

package cn.xym.leetcode;
    
    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    public class Solution {
            /**
    	 * 方法二：
    	 */
    	public boolean wordBreak2(String s, Set<String> dict){
    		int len = s.length();
    		boolean[] arrays = new boolean[len+1];
    		arrays[0] = true;
    		for (int i = 1; i <= len; ++i){
    			for (int j = 0; j < i; ++j){
    				if (arrays[j] && dict.contains(s.substring(j, i))){
    					// f(n) = f(0,i) + f(i,j) + f(j,n)
    					arrays[i] = true;
    					break;
    				}
    			}
    		}
    		return arrays[len];
    	}
    	/*
    	 * 方法一：
    	 * */
    	public boolean wordBreak1(String s, Set<String> dict) {
    		boolean flag = false;
    		int strLen = s.length();
            List<Integer> list = new ArrayList<Integer>();
            for (int i=strLen-1; i>=0; --i){
            	String endSubStr = s.substring(i);
            	if (dict.contains(endSubStr)){
            		list.add(i);
            	}else{
            		for(Integer n : list){
            			if (dict.contains(s.substring(i,n))){
            				list.add(i);
            				break;
            			}
            		}
            	}
            }
            if (list.isEmpty()){
            	flag = false;
            }else{
            	Integer n = list.get(list.size() - 1);
            	flag = n == 0 ? true : false;
            }
            return flag;
    	}
    	
    	
    	public static void main(String[] args) {
    		String s = "leetcode";
    		Set<String> dict = new HashSet<String>();
    		dict.add("leet");
    		dict.add("code");
    		Solution solution = new Solution();
    		System.out.println(solution.wordBreak2(s, dict));
    	}
    }

**题目：**

## Word Break II ##

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given  
s = `"catsanddog"`,  
dict = `["cat", "cats", "and", "sand", "dog"]`.

A solution is `["cats and dog", "cat sand dog"]`.

**分析：**

题目是跟上一题有点不一样的是，它需要把可能的所有情况都求出来，这样子的话，有了上一题的基础，我们可以在上体的基础上做一些处理就可以得到这题的答案哈。

**解题思路：**

这个题目是递归的一个典型的例子，有点像（M个数里面选K个数字）这个例子的变形。

举例说明：

s = `"catsanddog"`,  
dict = `["cat", "cats", "and", "sand", "dog"]`.

那么当检测到cat是属于dict中的话，这时候剩下的子串, "sanddog" 可能可以组成一个解。这时候我们把“cat”加入到一个解字符串(currentStr = "" )中，然后再去递归 "sanddog"这个字符串，当递归调用的字符串 s="" （即length == 0）时递归结束，证明这个解是成立的把 currentStr加入到 result中。

所有的递归结束了之后，把currentStr恢复到进入递归前的值，再继续往下判断“cats”  ... 这样一直下去直到字符串的最后一个字符!

具体的看代码哈，语言比较还是枯燥的，我觉得看着代码比较容易理解哈！

AC代码：

package copylist;
    
    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.Set;
    
    
    public class Solution {
    	
    	private ArrayList<String> result = new ArrayList<String>();
    	
    	
        public ArrayList<String> wordBreak(String s, Set<String> dict) {
        	//如果都没有解，那就没必要再往下求了，否则会TLE的
        	if (hasResult(s,dict)){
        		dfs(s, dict, "");
        	}
        	return result;
        }
        /*
         * 第一题 wordBreak I 判断字符串是否可由dict中的单词构成
         * 
         * */
        public boolean hasResult(String s, Set<String> dict){
        	int len = s.length();
        	if (s.length() == 0 || dict.size() == 0){
        		return false;
        	}
        	boolean[] arrays = new boolean[len+1];
        	arrays[0] = true;
        	for (int i=1; i<=len; ++i){
        		for (int j=0; j<i; ++j){
        			if (arrays[j] && dict.contains(s.substring(j,i))){
        				arrays[i] = true;
        				break;
        			}
        		}
        	}
        	
        	return arrays[len];
        }
        /**
         * 递归求解解的函数
         * @param subStr 要处理的字符串
         * @param dict   单词字典
         * @param currentStr  当前的解的字符串
         */
        public void dfs(String subStr, Set<String> dict, String currentStr){
        	/*递归结束的条件（解成立的条件）*/
        	if (subStr.length() == 0){
        		result.add(currentStr);
        	}
        	
        	for (int i=0; i<=subStr.length(); ++i){
        		String sub = subStr.substring(0,i);
        		/*包含这个子串的话，这个子串和剩余的子串有可能构成一组的解*/
        		if (dict.contains(sub)){
        			
        			//这个值是为了等下递归结束可以恢复currentStr的值
        			int subLen = currentStr.length();
        			
        			//如果不是解中的第一个单词，那么要在前加上一个空格 " "
        			if (!currentStr.equals("")){
        				currentStr += " ";
        			}
        			//加入到一个解的字符串中
        			currentStr += sub;
        			//递归
        			dfs(subStr.substring(i),dict,currentStr);
        			//恢复currentStr，继续下一个解的求解
        			currentStr = currentStr.substring(0,subLen);
        		}
        	}
        }
    }