拆分词句

//来个用set的
import java.util.*;
//定义一个set 把符合f（x） = true 的 x 放入set中
//1状态f（x）表示s.substring(0, x)是否可以符合条件
//2状态转移：遍历set中的所有元素num 若存在s.substring(num, x)在dic中 则为true 否则false
//3临界值：set为空时，只看s.substring(0, x)是否在dic中
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        //使用set来剪枝
        Set<Integer> set = new HashSet<>();
        set.add(0);
        for (int i = 0; i <= s.length(); i++) {
            Iterator<Integer> iter = set.iterator();
            boolean contains = false;
            while (iter.hasNext()) {
                int j = iter.next();
                if (dict.contains(s.substring(j, i))) {
                        contains = true;
                        break;
                } 
            }
            if (contains) {
                set.add(i);
            }
        }
            return set.contains(s.length());
    }
}

// 动态规划
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int N = s.length();
        // canBreak[i] 表示 s[0...i) 区间是否有若干个子串存在于 dict 中
        boolean[] canBreak = new boolean[N + 1];
        // 初始条件 canBreak[0] 为 true, s[0,0)区间为空区间, 想象为空集是任何集合的子集
        canBreak[0] = true;
        
        // 更新canBreak[1...N]的状态
        for(int i = 1; i <= N; i++) {
            // 记录从 s[j...i) 区间是否有若干子串存在于 dict 中
            for(int j = 0; j < i; j++) {
                // canBreak[j] 纪录了 s[0...j) 区间是否有若干个子串存在于 dict 中
                if(canBreak[j] && dict.contains(s.substring(j,i))) {
                    canBreak[i] = true;
                    break;
                } 
            }
        }
        return canBreak[N]; // canBreak[N] 纪录了 s[0...N) 区间是否有若干个子串存在于 dict 中
    }
}

// DFS
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        return canBreak(s, dict, 0, new int[s.length()]);
    }
    
    private boolean canBreak(String s, Set<String> dict, int b, int[] visited) {
        // [b,s.length) 此时为空区间
        if(b == s.length())
            return true;
        // visited纪录 s[b...s.length) 区间的访问状态
        // 0 -- 未访问
        // 1 -- s[b...s.length) 区间有若干子串存在于 dict 中
        // -1 -- s[b...s.length) 区间没有若干子串存在于dict 中
        if(visited[b] != 0)
             return visited[b] == 1;
        
        // 判断 s[b...s.length) 区间是否有若干子串存在于 dict 中
        for(int i = b + 1; i <= s.length(); i++) {
            // 如果 s[b...i) 包含于 dict 中, 则递归剩余区间查看是否有若干字串存在于 dict 中 
            if(dict.contains(s.substring(b,i)) && canBreak(s, dict, i, visited)) {
                // 如果 s[b...i) 和 s[i...s.length) 都为 true, 那么表示 s[b...s.length] 区间有若干子串存在于 dict 中
                visited[b] = 1;  // 更新状态
                return true;     
            }
        }
        // 如果循环走完, 为进入 if 则表示s[b...s.length] 区间没有若干子串存在于 dict 中
        visited[b] = -1;  // 更新状态
        return false;
    }
}

/**
 * 方法：动态规划
 * 状态：
 *      子状态：前1，2，3，...,n个字符能否根据词典中的词被成功分词
 *      F(i): 前i个字符能否根据词典中的词被成功分词
 * 状态递推：
 *      F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到}&nbs***bsp;false
 *      在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典
 *      中找到，则F(i)为true
 * 初始值：
 *      对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
 *      空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
 *      的例子进行验证
 *      F(0) = true
 * 返回结果：F(n)
 */
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] canBreak = new boolean[s.length() + 1];
        // 初始化F(0) = true
        canBreak[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // F(i): true{j < i && F(j) && substr[j+1,i]能在词典中找到}&nbs***bsp;false
                // 第j+1个字符的索引为j
                if (canBreak[j] && dict.contains(s.substring(j,i))) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
    }
}

import java.util.*;
public class Solution {
    static boolean sign = false;
    public boolean wordBreak(String s, Set dict) {
        if(s.length() == 0 || dict == null)return false;
        return DFS(s,dict);
    }
    public boolean DFS(String s, Set dict){
        if(s.length() == 0)sign = true;
        if(sign)return true;
        for(String str:dict){
            if(sign)return true;
            if(s.startsWith(str)){
                DFS(s.substring(str.length()),dict);
            }
        }
        return sign;
    }
}

这个样例数据很有问题啊，明明输出没问题，本地没问题，到牛客上就过不了（他自己的显示也有问题），看了好多其他的答案都可以a,不知道自己的问题出在哪里

private ArrayList<String> res = new ArrayList<>();
/**
 * 动态规划（我为什么要用动态规划。。题目要求的。。。）
 *
 * 状态转移方程：f(n) = f(i) + String(i+1,n)    0 <= i < n
 *
 * dp[i]存的是当前子串的开始索引，i是子串的结束索引
 * dp[i]链表长度为0代表不能被分割
 * 最后用递归获取所有可能的字符串
 *
 * 时间复杂度：O(n)+O(n^2)+O(m) m为结果个数
 */
public ArrayList<String> wordBreak(String s, Set<String> dict) {
    if (s == null || dict == null || dict.size() == 0) return res;
    if (s.equals("")) {
        if (dict.contains("")) {
            res.add("");
            return res;
        }
        return res;
    }
    ArrayList<ArrayList<Integer>> dp = new ArrayList<>();
    for (int i = 0; i <= s.length(); i++) {
        dp.add(new ArrayList<>());
    }
    dp.get(0).add(0);
    for (int i = 1; i <= s.length(); i++) {
        ArrayList<Integer> list = dp.get(i);
        for (int j = i - 1; j >= 0; j--) {
            ArrayList<Integer> listj = dp.get(j);
            String t = s.substring(j, i);
            if (listj.size() != 0 && dict.contains(t)) {
                list.add(j);
            }
        }
    }
    if (dp.get(s.length()).size() != 0) {
        StringBuilder sb = new StringBuilder();
        getResult(s, dp, sb, s.length());
    }
    return res;
}
private void getResult(String s, ArrayList<ArrayList<Integer>> dp, StringBuilder temp, int index) {
    if (index == 0) {
        res.add(temp.toString());
        return;
    }
    ArrayList<Integer> list = dp.get(index);
    for (int i = 0; i < list.size(); i++) {
        if (index == s.length()) {
            temp.append(s, list.get(i), index);
        } else {
            temp.insert(0, s.substring(list.get(i), index) + ' ');
        }
        getResult(s, dp, temp, list.get(i));
        if (index == s.length()) {
            temp.delete(0, index - list.get(i));
        } else {
            temp.delete(0, index - list.get(i) + 1);
        }
    }
}

简单的 dp 解法：

import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

import java.util.HashSet;
import java.util.Set;
public class Solution {     /*      * f(i)表示s[0,i]是否可以分词      * 动态转移方程：f(i)=f(j) && f(j+1,i);0<=j<i      */     public boolean wordBreak(String s, Set<String> dict) {         boolean[] f=new boolean[s.length()+1];         f[0]=true;         for(int i=1;i<=s.length();i++){             for(int j=0;j<i;j++){                 if(f[j]&&dict.contains(s.substring(j,i))){                     f[i]=true;                     break;                 }             }         }         return f[s.length()];     }
}

//有几个需要注意的边界点
import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int i,j;
        boolean array[]=new boolean[s.length()+1];//此处的Array大小
        array[0]=true;//此处的初始化
        for(i=1;i<array.length;i++) {
            for(j=0;j<i;j++) {
                if(array[j]&&dict.contains(s.substring(j, i))) {
                    array[i]=true;//此处的SubString
                    break;
                }
            }
        }
        return array[array.length-1];//此处的返回值
    
    }
}

import java.util.*;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        boolean[] booleans = new boolean[len + 1];//从下标0开始i个字符是否可分
        booleans[0] = true;
        for (int i = 1; i <= len; i++) {//s[0..i-1]
            for (int j = i - 1; j >= 0; j--) {
                if (dict.contains(s.substring(j, i)) && booleans[j]) {
                    booleans[i] = true;
                    break;
                }
            }
        }
        return booleans[len];
    }
}

import java.util.Set;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        /*
        分析:
        动态规划:原问题可以划分为若干个子问题且子问题具有重叠性
        求解:保存已获取的子问题的解，用于求未解的子问题
        B[i]=true表示字符串s[0]~s[i-1]可以通过dict分解
        即前i个字符组成的字符串可以被字典分解
        初始时设B[0]=true,
        分解式:B[j]=B[i]&&dict.contains(sij-1),j由遍历dict得到
        (即遍历dict获取使得dict.contains(sij-1)为true的j)，更新B[j]
        求B[n]即s[0]~s[n-1]是否可分解
        */
        boolean []B = new boolean[s.length()+1];//多出的一个存放初始B[0]
        B[0] = true;//初始值
        for(int i=0;i<s.length();i++){//每一次循环获取一个B[i]的值,最终得到B[n]
            if (B[i]){//B[i]=true，通过B[i]来确定下一个使得B[j]=true的j
                for(String sub:dict){//查找最小的i使得B[i]=true
                    int j = i+sub.length();
                    if (j<=s.length()){
                        String substr = s.substring(i,j);//取子串s[i,i+sub.length())
                        if (substr.equals(sub)){//B[j]=B[i]&&dict.contains(sij-1)
                            B[j] = true;
                        }
                    }
                }
            }//默认未置为true的B[i]为false
        }
        return B[s.length()];//最终返回结果B[n]
    }
}

import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        return wb(len,dict,s);
    }
    public boolean wb(int len, Set<String> dict, String s){
        if(len == 0)
            return true;
        for(int i = len-1; i >=0; i--){
            if(dict.contains(s.substring(i,len))){
                if(wb(i,dict,s))
                    return true;
            }
        }
        return false;
    }
}

动态规划思想
import java.util.Set;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        // dp[i]表示0到i位可分
        boolean[] dp = new boolean [len+1];
        dp[0] = true;	//0到0可分
        for(int i = 1; i <= len; i ++){
            for(int j = 0; j < len; j ++){
                //如果 0-j可分，并且dic中包含j-i 的子串，那么0-i 为可分
                if(dp[j] && dict.contains(s.substring(j,i))){
                    dp[i] = true;
                }
            }
        }
        return dp[len];
    }
}

import java.util.Set;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s == null || "".equals(s.trim()) || dict == null || dict.isEmpty()){
            return false;
        }
        boolean dp[] = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i; dp[i] && j < s.length(); j++){
                if (dict.contains(s.substring(i, j+1)))
                	dp[j+1]=true;
            }
        }
        return dp[s.length()];
    }
}

import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0)
            return false;
        boolean[] isWords = new boolean[s.length() + 1];
        isWords[0] = true;
        for (int i = 0; i < s.length(); i++) {
            isWords[i + 1] = false;
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < i + 1; j++) {
                if (isWords[j]) {
                    if (dict.contains(s.substring(j, i + 1))) {
                        isWords[i + 1] = true;
                        break;
                    }
                }
            }
        }
        return isWords[s.length()];
    }
}

public class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean[] f = new boolean[s.length() + 1];
        
        f[0] = true; /* First DP
        for(int i = 1; i <= s.length(); i++){
            for(String str: dict){
                if(str.length() <= i){
                    if(f[i - str.length()]){
                        if(s.substring(i-str.length(), i).equals(str)){
                            f[i] = true;
                            break;
                        }
                    }
                }
            }
        }*/ //Second DP for(int i=1; i <= s.length(); i++){ for(int j=0; j < i; j++){ if(f[j] && dict.contains(s.substring(j, i))){
                    f[i] = true; break;
                }
            }
        } return f[s.length()];
    }
}