如何检查一个单词是否可以由数组中的条目组成?
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()];
}
我有以下任务:
给出了一个词"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()];
}