LeetCode-140

题目

结果

代码

class Solution {
    // 存储结果
    private final List<String> ans = new LinkedList<>();
    // 将s作为全局变量
    private String target;

    public List<String> wordBreak(String s, List<String> wordDict) {
        // 预判断
        if (!quickJudge(s, wordDict)) {
            return ans;
        }
        // 将s作为全局变量
        this.target = s;
        TreeNode root = new TreeNode("root");
        buildTree(s, wordDict, root);
        for (TreeNode node : root.getChildren()) {
            dfs(node, "");
        }
        return ans;
    }

    private void dfs(TreeNode root, String str) {
        // 如果是叶子节点
        if (root.getChildren().size() == 0) {
            str += root.getVal();
            if (str.replaceAll(" ", "").equals(this.target)) {
                ans.add(str);
            }
            return;
        } else { // 如果不是叶子节点
            str += root.getVal() + " ";
        }
        // 递归
        for (var node : root.getChildren()) {
            dfs(node, str);
        }
    }

    // 递归建树
    private void buildTree(String s, List<String> dict, TreeNode root) {
        for (var word : dict) {
            if (s.startsWith(word)) {
                TreeNode node = new TreeNode(word);
                root.getChildren().add(node);
                int index = word.length();
                buildTree(s.substring(index), dict, node);
            }
        }
    }

    // 判断s中是否有dict不含的字母
    private boolean quickJudge(String s, List<String> dict) {
        Set<Character> set = new HashSet<>();
        for (String str : dict) {
            for (char ch : str.toCharArray()) {
                set.add(ch);
            }
        }
        for (char ch : s.toCharArray()) {
            if (!set.contains(ch)) {
                return false;
            }
        }
        return true;
    }
}

class TreeNode {
    private String val;
    private final List<TreeNode> children;

    public String getVal() {
        return val;
    }

    public List<TreeNode> getChildren() {
        return children;
    }

    TreeNode(String x) {
        children = new LinkedList<>();
        val = x;
    }
}

复杂度

时间复杂度：不知道replaceAll这种函数复杂度是多少

空间复杂度：不计其数