如何检查一个单词是否可以由数组中的条目组成?

How to check if a word can be composed of entries in an array?

我有以下任务:

给出了一个词"Superhighway"。 检查这样的词是否可以由数组中的条目组成: [ab, bc, Super, h, igh, way] - 是; [ab, bc, Super, way] - 否;

我的建议是从数组构建Trie树,根据Trie树判断是否可以推导出目标词。

另外,我看到动态规划也适用于类似的问题。

能否解释一下该任务的最佳解决方案?

这里应该应用动态规划。这里的最优子结构是:

dp[i]: 如果 s[0, i) 可以由提供数组中的条目组成。

dp[i] |= dp[j] && (s[j, i) 是数组中的一个条目)。

        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> wordDictSet = new HashSet(wordDict);
            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] && wordDictSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }