139. Word Break 拆分词句

难度 medium

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

解题思路：这道题最直接的方法是使用动态规划，dp[i]表示从0到i的位置是否可以分割，如果可以，置为1，则dp最后一个元素表示整个字符串是否可分割，用一个set保存所有单词，从头遍历字符串，需要用两轮循环，外循环i从0到len， 内循环j从0到i，分割出字符串的[j, i)部分，如果在set中存在且dp[j]=1，则将dp[i]也置为1，表示i这个位置满足，同时break掉，两轮循环可以遍历完整个字符串，最后也就知道了整个字符串是否可以拆分。
代码t68 s57 java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        int[] dp = new int[len+1];
        HashSet<String> set = new HashSet<>();
        set.addAll(wordDict);
        dp[0] = 1;
        for(int i=0; i<=len; i++){
            for(int j=0; j<i; j++){
                if(dp[j]==1 && set.contains(s.substring(j, i))){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[len]==1 ? true : false;
    }
}

解题思路：
用一个set保存wordDict中的单词，用于快速查找，用一个memo数组保存计算过的结果，memo[i]表示[i,n]这段字符串是否可拆，初始化为-1，变量start保存当前遍历到的位置，初始化为0，进入递归函数，递归函数的功能就是判断一段字符串是否可以被分割，如果start已经到了字符串的最后一个元素+1的位置，说明整个字符串都遍历完了，直接返回true，如果memo[start]不为-1，说明已经遍历过了，那就看memo是否为1，1表示可以切分，0表示不能切分，依次返回true和false，这是为了防止重复遍历，然后从start开始直到字符串结尾，截取[start,i)这一段，判断是否在set中，同时以i为起点进入递归函数，判断剩下的部分能否被切分，如果二者都能满足，说明i这个位置是符合题意的，将memo[i]置为1，返回true，当整个字符串遍历完了都无法拆分，则将memo[start]置为0，表示[start,n]这段字符串不可拆，返回false。

代码 t78 s7 java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        set.addAll(wordDict);
        int n = s.length();
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return helper(s, set, 0, memo);
    }

    public boolean helper(String s, HashSet<String> set, int start, int[] memo){
        if(start>=s.length()) return true;
        if(memo[start]!=-1) return memo[start]==1 ? true : false;
        for(int i=start+1; i<=s.length(); i++){
            if(set.contains(s.substring(start, i)) && helper(s, set, i, memo)){
                memo[start] = 1;
                return true;
            }
        }
        memo[start] = 0;
        return false;
    }
}

这是之前提交的cpp版本的。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> memo(s.size(), -1);
        return check(s, wordSet, 0, memo);
    }
    bool check(string s, unordered_set<string>& wordSet, int start, vector<int>& memo) {
        if (start >= s.size()) return true;
        if (memo[start] != -1) return memo[start];
        for (int i = start + 1; i <= s.size(); ++i) {
            if (wordSet.count(s.substr(start, i - start)) && check(s, wordSet, i, memo)) {
                return memo[start] = 1;
            }
        }
        return memo[start] = 0;
    }
};

相似题目：
140. 单词拆分 II

参考资料：
http://www.cnblogs.com/grandyang/p/4257740.html

139. Word Break 拆分词句

原文：https://www.cnblogs.com/zhengxch/p/14800622.html