给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

记忆化搜索

import java.util.Arrays;
import java.util.List;

class Solution {

    private Trie trie;

    private Boolean[] dp;

    private boolean solve(String s, int index) {
        if (index == s.length()) {
            return true;
        }

        if (dp[index] != null) {
            return dp[index];
        }

        Trie.Node cur = trie.getRoot();

        boolean ret = false;

        for (int i = index; i < s.length(); ++i) {
            int path = s.charAt(i) - 'a';
            if (cur.children[path] != null) {
                cur = cur.children[path];
                if (cur.end && solve(s, i + 1)) {
                    ret = true;
                    break;
                }
            } else {
                break;
            }
        }

        dp[index] = ret;

        return ret;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        this.trie = new Trie();
        this.dp = new Boolean[s.length()];
        this.trie.addAll(wordDict);
        return solve(s, 0);
    }
}

class Trie {

    private Node root = new Node();


    class Node {
        Node[] children;
        int pass;
        boolean end;

        public Node() {
            this.children = new Node[26];
            this.pass = 0;
            this.end = false;
        }
    }

    public Node getRoot() {
        return this.root;
    }

    public void addAll(List<String> wordDict) {
        for (String word : wordDict) {
            insert(word);
        }
    }


    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        Node cur = root;
        for (int i = 0; i < word.length(); ++i) {
            int path = word.charAt(i) - 'a';
            if (cur.children[path] == null) {
                cur.children[path] = new Node();
            }
            cur = cur.children[path];
            cur.pass++;
        }
        cur.end = true;
    }

}

动态规划

import java.util.List;

class Solution {

    private Trie trie;

    private boolean solveDp(String s) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[n] = true;

        for (int index = n - 1; index >= 0; --index) {
            Trie.Node cur = trie.getRoot();
            for (int i = index; i < n; ++i) {
                int path = s.charAt(i) - 'a';
                if (cur.children[path] != null) {
                    cur = cur.children[path];
                    if (cur.end && dp[i + 1]) {
                        dp[index] = true;
                    }
                } else {
                    break;
                }
            }
        }

        return dp[0];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        this.trie = new Trie();
        this.trie.addAll(wordDict);
        return solveDp(s);
    }
}

class Trie {

    private Node root = new Node();


    class Node {
        Node[] children;
        int pass;
        boolean end;

        public Node() {
            this.children = new Node[26];
            this.pass = 0;
            this.end = false;
        }
    }

    public Node getRoot() {
        return this.root;
    }

    public void addAll(List<String> wordDict) {
        for (String word : wordDict) {
            insert(word);
        }
    }


    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        Node cur = root;
        for (int i = 0; i < word.length(); ++i) {
            int path = word.charAt(i) - 'a';
            if (cur.children[path] == null) {
                cur.children[path] = new Node();
            }
            cur = cur.children[path];
            cur.pass++;
        }
        cur.end = true;
    }

}