139.Word Break (M)

1.Description(Medium)

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

Example

Given s ="lintcode", dict =["lint", "code"].

Return true because"lintcode"can be break as"lint code".

2.Code

Solution 1:DFS

看到这题第一反应是DFS枚举查找，直到“探”到string尾部则算成功。但题目并不要求给出是如何break的，而只要判断是否能break。对这类判断“是”与“否”的可以用DFS暴力解决的题.

对于这道题，我们首先考虑暴力的方法。本题相当于用多个字符串组成该字符串，那么我们就枚举所有可能的放入字符串的方法，通过深度优先搜索，尝试所有可能。 对于一个字符串，考虑字典中的每个前缀是否是这个字典中的单词。若不是，则跳过该单词。若是则将该前缀从字符串中删除后，判断剩下的字符串能否由字典里的单词组成。 由于题目的数据加强，此题已经无法使用常规的DFS方式通过，我们更推荐更优秀的DP来实现。

代码思路

使用深度优先搜索，记录字符串，字典，以及当前需要判断的字符串的起始点 从当前字符串的起始点开始判断

代码框架

定义dfs
    递归的出口
    如果起始点已经在字符串的尾部
        停止，返回可以组成该字符串
    如果还未到结尾，枚举下一个字符串的长度。
        对于每种可能，判断该字符串是否在字典中
        如果在字典中：
            取出该字符串，判断剩下的是否可以
    找完所有可能后，仍然不行，直接返回这段字符串无法找到答案
    
    

时间复杂度：O(2^n)，考虑当s = "aaaaaaaaaaab", dict = {"a", "aa", "aaa", ...., "aaaaaaaaa"} 空间复杂度：O(N)，递归深度最深为N层

相关问题：

LintCode 582. Word Break II LintCode 683. Word break III LintCode 123. Word Search

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        return dfs(s, dict, 0); 
    }
    
    /**
     * 递归的定义
     * 判断字符串s[start: ]能否通过wordDict中的单词组成
    **/
    public boolean dfs(String s, Set<String> dict, int now) {
        // 递归的出口
        if (now == s.length()) {
            return true;
        }
        
        // 递归的拆解，枚举下一个字符串的长度len
        for (int len = 1; now + len <= s.length(); len++) {
            // 判断s[now: now + len]是否满足条件
            if (dict.contains(s.substring(now, now + len)) && dfs(s, dict, now + len)) {
                return true;
            }
        }
        return false;
    }
}

Solution 2: Dynamic Programming

state: f[i] 表示前i个字符能不能被完美切分。

function：f[i] = OR{f[j]}+ j+1~i is a word (优化：j只需要到最长的单词长度即可)

例: j=0,1,3,5 f[i] =f[0] || f[1] || f[3] || f[5]

Initialize: f[0]=true

answer:f[n]

 public boolean wordBreak(String s, Set<String> dict) {

         if (s == null || s.length() == 0) {
             return true;
         }

        int n=s.length();

        int maxlen=0;
        for(String str:dict){
            int len=str.length();
            if(len>maxlen){
                maxlen=len;
            }
        }

        //state;
        boolean[] cut=new boolean[n+1];

        //Initialize:
        cut[0]=true;

        //function:
        for(int i=1;i<=n;i++){
            cut[i]=false;
            for(int lastwordlength=1;
                    lastwordlength<=maxlen && lastwordlength<=i;
                    lastwordlength++){

            String word=s.substring(i-lastwordlength, i);
                if(cut[i-lastwordlength] && dict.contains(word)){
                    cut[i]=true;
                    break;
            }
        }
    }
        return cut[n];


    }