题目主要信息

1、给定一个字符串和一个字符串数组

2、判断字符串能否拆分成若干个字符串符合字符串数组的子集

方法一:动态规划

具体方法

可以使用动态规划的方法，dp[i]表示以第i个字符结尾的字符串是否满足该条件。

因此当字符串从i到j的子字符串属于字符串数组时，满足dp[i]=dp[i-j]。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串一维数组 
     * @return bool布尔型
     */
    public boolean wordDiv (String s, String[] dic) {
        // write code here
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1; i<=s.length(); i++){
            for(String str : dic){
                if(str.length()<=i){ 
                    if(str.equals(s.substring(i-str.length(), i))){  //判断是否有字符串与子字符串相同
                        dp[i] = dp[i-str.length()];
                    }
                }
            }
        }
        return dp[s.length()];
    }
}

复杂度分析

• 时间复杂度：$O(n\ast l1\ast l2)O(n*l1*l2)$，其中n为数组长度，l1为字符串长度，l2为数组中字符串长度
• 空间复杂度：$O(l1)O(l1)$，动规数组，长度为l1

方法二：动态规划+前缀树

具体方法

在方法一中，主要的时间复杂度在于每次都需要判断是否有对应的字符串与子字符串相同，可以对字符串数组建立前缀树，通过查找前缀树来减少时间复杂度。

注意，由于从后向前搜索，构建倒序前缀树。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串一维数组 
     * @return bool布尔型
     */
    public boolean wordDiv (String s, String[] dic) {
        // write code here
        Trie trie = new Trie();
        for(String str:dic){
            trie.addWord(new StringBuilder(str).reverse().toString());
        }
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1; i<=s.length(); i++){
            dp[i] = trie.isContains(s, dp, i);
        }
        return dp[s.length()];
    }
}
class Trie {
    private static TrieNode root;
    
    public Trie(){
        root = new TrieNode();
    }

    public static void addWord(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        // 每次调用addWord都重新拿到全局根节点对象
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char code = word.charAt(i);
            // 增加字母, 并且返回子节点继续增加
            current = current.add(code);
        }
        current.end = true;
    }
    public boolean isContains(String s, boolean[] dp, int i) {
        String text = new StringBuilder(s.substring(0, i)).reverse().toString();
        // 获得前缀树
        TrieNode current = root;
        // 从词的首位开始遍历
        int index = 0;
        boolean flag = false;
        while (index < text.length()) {
            // 如果在当前层找到当前字母，继续往下一层找
            if (current.child.get(text.charAt(index)) != null) {
                current = current.child.get(text.charAt(index));
            } else {
                // 如果在当前这一层找不到字符子节点，则结束循环
                break;
            }
            // 判断是否存在的依据： 当前查找返回的节点对象是否是end，如果是，根据dp数组进行判断
            if (current.end) {
                if(dp[i-index-1]){
                    flag = true;
                }
            }
            index += 1;
        }
        return flag;
    }


    private static class TrieNode {
        public char value;
        public Map<Character, TrieNode> child = new HashMap<>();
        private boolean end = false;

        public TrieNode() {
        }

        public TrieNode add(char newChar) {
            if (child == null) {
                this.child = new HashMap<>();
            }
            // 找到对应字符的字典树
            TrieNode t = child.get(newChar);
            // 在map中查找是否已经存在字母
            if (t == null) {
                // 不存在则新建一个节点对象
                t = new TrieNode();
                // 给节点对象命名为该字母
                t.value = newChar;
                child.put(newChar, t);
            }
            // 返回下一个节点
            return t;
        }
    }
}

复杂度分析

• 时间复杂度：$O(max(n\ast l2\mathrm{，}l1\ast l2))O(max(n*l2，l1*l2))$，构建字符串前缀树的时间复杂度为$O(n\ast l2)O(n*l2)$，后续查找时间复杂度为$O(l1\ast l2)O(l1*l2)$
• 空间复杂度：$O(l1)O(l1)$或$O(n\ast l2)O(n*l2)$