方法1：递归

很明显，这是个递归的问题。我们应该能比较轻松的写出下面的代码：

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

但是这个代码在执行下面的测试样例（这个样例是在LeetCode上拿到的）时，会超时。
。
为什么会这样呢？想一个简单一点的，s的值为aaaaab，dict的值为"a", "aa", "aaa", "aaaa", "aaaaa",那递归下去，第一次递归结束，是a不匹配b。然后再去循环判断ab中的每个子串是否在dict中，然后再去判断aab中每个子串是否在dict中。有没有发现什么，aab中，ab子串已经判断过了，递归的过程中又进行了一次重复判断。这样，这上面的方法的时间复杂度就是O(nⁿ)，时间复杂度超级高了。那既然有很多重复判断，我们何不用一个容器将以前判断的结果记录下来，后面判断的时候直接用呢。所以有了下面优化的版本：

import java.util.*;
public class Solution {
    HashMap<String,Boolean> flag=new HashMap<>();
    public boolean wordBreak(String s, Set<String> dict) {
        if (s.length()==0)
            return true;
        if (flag.containsKey(s))
            return flag.get(s);
        for (int i=1;i<=s.length();++i){
            String sub=s.substring(0,i);
            boolean b=dict.contains(sub);
            flag.put(sub,b);
            if (b&&wordBreak(s.substring(i),dict))
                return true;
        }
        return false;
    }
}

但是这种太占内存了，当字符串长度很长的时候，其子串会非常多，导致HashMap占用内存非常大。搬运LeetCode里面的解法，代码如下：

public boolean wordBreak(String s, Set<String> wordDict) {
        return word_Break(s, wordDict, 0, new Boolean[s.length()]);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }

方法2：动态规划

讨论里面很多都是用动态规划的方法做的，其基本原理是将一个字符串分成两个部分，如果两个部分都满足要求，则总的字符串是满足要求的，这两个部分又可以继续去判断。具体代码如下：

    public boolean wordBreak(String s, Set<String> wordDict) {
        int len = s.length();

        boolean[] flags = new boolean[len+1];
        flags[0] = true;

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (flags[j] == true && wordDict.contains(s.substring(j,i))) {
                    flags[i] = true;
                    break;
                }
            }
        }

        return flags[len];
    }

方法3：BFS

搬运自LeetCode官方题解，自己跑一遍应该能看懂。

    public boolean wordBreak(String s, Set<String> dict) {
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[s.length()];
        queue.add(0);
        while (!queue.isEmpty()) {
            int start = queue.remove();
            if (visited[start] == 0) {
                for (int end = start + 1; end <= s.length(); end++) {
                    if (dict.contains(s.substring(start, end))) {
                        queue.add(end);
                        if (end == s.length()) {
                            return true;
                        }
                    }
                }
                visited[start] = 1;
            }
        }
        return false;
    }

但上面的代码还有优化的空间。我们看到，红框部分，是从end到s.length遍历的，对应的子串长度为end-start。这就导致，有一些不可能出现的子串被判断了。假设dict中，最长的单词为3个字母，那当(end-start)>3时，就没必要再去判断了。

所以，我们再做一下优化，优化代码如下：

    public boolean wordBreak(String s, Set<String> dict) {
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[s.length()];
        queue.add(0);
        //扫描一遍dict，记录最长的单词长度
        int maxLen=-1;
        for (String item:dict){
            if (item.length()>maxLen)
                maxLen=item.length();
        }
        while (!queue.isEmpty()) {
            int start = queue.remove();
            if (visited[start] == 0) {
                for (int end = start + 1; end <= s.length(); end++) {
                    if ((end-start)<=maxLen&&dict.contains(s.substring(start, end))) {
                        queue.add(end);
                        if (end == s.length()) {
                            return true;
                        }
                    }
                }
                visited[start] = 1;
            }
        }
        return false;
    }

经过测试，使用BFS的优化过的效率最高。