要解决的问题：
给定一个非空字符串s和一个包含列表的字符串阵列wordarr 在非空的单词中，确定是否可以将S分割成 一个或多个字典单词的空间分隔序列。您可以 假设字典不包含重复的单词。
例如，给定的s =" leetcode"，wordarr = [" leet"，" code"]。
返回true，因为" leetcode"可以分割为" leet代码"。
在上述问题中，它可以构建一个在wordArr中具有每个字符串的TRIE。然后，对于给定的字符串s中的每个字符，请沿着Trie工作。如果Trie分支终止，则该子字符串已完成，因此将其余的字符串传递到根部，并递归地进行完全相同的事情。
这应该是o（n）时间，o（n）空间正确吗？我之所以问，因为我正在处理的问题说这将是最佳的时间（n^2）时间，我不确定我的方法怎么了。
例如，如果s = "hello"和wordArr = ["he", "ll", "ee", "zz", "o"]，则"he"将在TRIE的第一个分支中完成，"llo"将递归传递到根。然后，"ll"将完成，因此"o"被传递到Trie的根。然后"o"完成，这是s的末尾，因此返回true。如果s的末尾尚未完成，请返回false。
这是正确的吗？
您的示例确实暗示了线性时间的复杂性，但请查看此示例：
s = "hello"
wordArr = ["hell", "he", "e", "ll", "lo", "l", "h"]
现在，尝试了第一个"地狱"，但是在下一个递归周期中，找不到解决方案（没有" o"），因此算法需要回溯，并假设"地狱"不合适（双关语不打算），所以您尝试"他"，在下一个层次上，您会发现" ll"，但随后又失败了，因为没有" o"。再次需要回溯。现在以" H"，然后是" E"开始，然后再次发生故障：您尝试" LL"而无需成功，因此可以回溯使用" L"：解决方案现在可用：" H e l lo"。
所以，没有它没有 o（n）时间复杂性。
我怀疑问题正在回溯。如果该单词无法基于特定词典进行分割，或者如果有多个可能的子字符串具有常见前缀，该怎么办？例如，假设字典包含he，llenic和llo。失败落下Trie的一个分支将需要回溯，并且时间复杂性的相应增加。
这类似于一个正则匹配问题：您给出的示例就像测试一个针对
的输入单词^(he|ll|ee|zz|o)+$
（任何数量的词典成员，按任何顺序，什么都没有）。我不知道Regex Matchers的时间复杂性，但我知道回溯会使您陷入严重的时间麻烦。
我确实找到了这个答案：
对字符串运行DFA进行的正则表达式确实是O（n），但最多需要O（2^m）构建时间/空间（其中M =正则表达式）。
所以也许是o（n^2），并减少了施工工作。
让我们首先将Trie转换为NFA。我们在根上创建一个接受节点，并添加一个从trie中的每个单词末端移动到空char的根节点的边缘。
时间复杂性：由于Trie中的每个步骤，我们只能移动到一个表示输入字符串和根中当前字符的边缘。t（n）= 2×t（n-1） c这给了我们o（2^n）
确实不是o（n），但是您可以使用动态编程做得更好。
- 我们将使用自上而下的方法。
- 在我们解决该字符串之前，请检查是否已经解决。
- 我们可以使用另一个哈希图来存储已经解决的字符串的结果。
- 每当任何递归调用返回false时，将该字符串存储在哈希玛普中。
这个想法是仅计算单词的每个后缀一次。我们只有n个后缀，最终将以o（n^2）。
代码表格algorithms.tutorialhorizon.com：
Map<String, String> memoized;
Set<String> dict;
String SegmentString(String input) {
if (dict.contains(input)) return input;
if (memoized.containsKey(input) {
return memoized.get(input);
}
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix);
if (segSuffix != null) {
memoized.put(input, prefix + " " + segSuffix);
return prefix + " " + segSuffix;
}
}
您可以做得更好！
Map<String, String> memoized;
Trie<String> dict;
String SegmentString(String input)
{
if (dict.contains(input))
return input;
if (memoized.containsKey(input)
return memoized.get(input);
int len = input.length();
foreach (StringBuilder word in dict.GetAll(input))
{
String prefix = input.substring(0, word.length);
String suffix = input.substring(word.length, len);
String segSuffix = SegmentString(suffix);
if (segSuffix != null)
{
memoized.put(input, word.ToString() + " " + segSuffix);
return prefix + " " + segSuffix;
}
}
retrun null;
}
使用trieto才能在trie到达单词结尾时才能找到递归调用，您将获得o（z×n），其中z是trie的长度。