我遇到了一个称为“断词问题”的编程难题,大意如下:
给定一个输入字符串和一个单词字典,如果可能的话将输入字符串分割成以空格分隔的一系列单词。
例如,如果输入字符串是“applepie”,并且字典包含标准的英语单词集合,则我们将返回字符串“apple pie”作为输出。
我自己想出了一个二次时间复杂度的解决方案。我还发现了各种使用DP的其他二次时间复杂度的解决方案。
然而,在Quora上,有一个用户发布了一个线性时间复杂度的解决方案。
我无法理解它如何成为线性的。时间复杂度计算中有错误吗?这个问题的最坏情况时间复杂度是什么?我在此发布最常见的DP解决方案。
给定一个输入字符串和一个单词字典,如果可能的话将输入字符串分割成以空格分隔的一系列单词。
例如,如果输入字符串是“applepie”,并且字典包含标准的英语单词集合,则我们将返回字符串“apple pie”作为输出。
我自己想出了一个二次时间复杂度的解决方案。我还发现了各种使用DP的其他二次时间复杂度的解决方案。
然而,在Quora上,有一个用户发布了一个线性时间复杂度的解决方案。
我无法理解它如何成为线性的。时间复杂度计算中有错误吗?这个问题的最坏情况时间复杂度是什么?我在此发布最常见的DP解决方案。
String SegmentString(String input, Set<String> dict) {
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);
if (dict.contains(suffix)) {
return prefix + " " + suffix;
}
}
}
return null;
}
expertsexchange => [expert, sex, change], [experts, exchange]
- mishadoff