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. You may assume the dictionary does not contain duplicate words.

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

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

s = "bb",
dict=["b"]
return true because "bb" can be segmented as "b b".

大意就是把给定的字符串是否能按照给定的list分割开来
这道题目有3种解法，DFS，BFS和DP。

首先看DFS

    public boolean wordBreak(String s, List<String> dict) {
        Set<Integer> cache = new HashSet<Integer>();
        return dfs(cache, s, dict, 0);
    }

    private boolean dfs(Set<Integer> cache, String s, List<String> dict, int index){
        if(s.length() == index){
            return true;
        }

        /**
         * 注意缓存的使用
         * 请考虑在s=aaab，dict=["a","aa","aaa"]的情况
         * 递归到str=b的情况dfs方法返回false
         * 之后返回上一层递归str=ab,依然返回false
         * 在返回上一层递归str=aa,再次进入dfs方法，省去了单独判断b的情况
         * 考虑当s=aaaaaaaaaaaaaaaaa.....aaaab的时候，这样是十分节省效率的
         */
        if(cache.contains(index)){
            return false;
        }

        for(int i = index + 1; i <= s.length(); i++){
            String str = s.substring(index, i);
            if(dict.contains(str)){
                if(dfs(cache, s, dict, i)){
                    return true;
                }else{
                    cache.add(i);
                }
            }
        }
        cache.add(index);

        return false;
    }

在看BFS算法实现

    public boolean wordBreak(String s, List<String> dict) {
        if (dict.contains(s)) {
            return true;
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(0);
        Set<Integer> visited = new HashSet<Integer>();
        visited.add(0);
        while (!queue.isEmpty()) {
            int curIdx = queue.poll();
            for (int i = curIdx+1; i <= s.length(); i++) {
                /**
                 * 缓存和dfs方法使用的情况一样
                 * 如果有解的话都直接返回了true，如果再次作为路径被轮询到
                 * ，那么不用重复判断，从该点出发的路线一定会被走到，没必要再走一次
                 * 用代码的话说就是不用再压到queue里，因为queue里已经有了
                 */
                if (visited.contains(i)) {
                    continue;
                }
                if (dict.contains(s.substring(curIdx, i))) {
                    //最优解找到
                    //因为i<=s.length()所以总会有i == s.length()的时候
                    //所以最优解还需要一个限制条件就是dict.contains(s.substring(curIdx, i))
                    if (i == s.length()) {
                        return true;
                    }
                    //保证每次开始寻址的起点都存在dict中
                    queue.offer(i);
                    visited.add(i);
                }
            }
        }
        return false;
    }

最后看dp算法

    public boolean wordBreak(String s, List<String> dict) {
        //dp[i]表示s[0:i]可以在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()];
    }