A*********t
发帖数: 64 | 1 算法一：DFS，当然aaaaaaaaaaaaaaaa就超时了。
算法二：DP, O(n^3), dp[i][len]纪录,每次查找O(n)。
算法三：DP, O(n^2), Java用HashSet，C++用unordered_set，理论上每次query是O(1)。
20行就写完了。
那么有没有小于这个的算法呢？比如严格o(n^2)，O(nlogn)的. |
s**x
发帖数: 7506 | 2 can you post your code for n^2? |
h****n
发帖数: 1093 | 3 bool wordBreak(string s, unordered_set &dict) {
int N = s.size();
vector dp(N+1, false);
dp[0] = true;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= i; j++) {
if (dp[i-j] && (dict.find(s.substr(i-j, j)) != dict.end())) {
dp[i] = true;
break;
}
}
return dp[N];
} |
p***e
发帖数: 111 | 4 就我一外行来看，你这个不是dp呀。这个不就是O(n^2)的暴力解法嘛。不能因为变量名
字是dp,就叫dp算法吧。
><= i;="" j++)="" {="" :="" if="" (dp[i-j]="" &&="" (dict.find(s.substr(
i-j,="" j))="" !="dict.end()))" {="" :="" dp[i]="true;" :="" break;="" :=""
}="" :="" ...................="">
【在 h****n 的大作中提到】
: bool wordBreak(string s, unordered_set &dict) {
: int N = s.size();
: vector dp(N+1, false);
: dp[0] = true;
: for (int i = 1; i <= N; i++)
: for (int j = 1; j <= i; j++) {
: if (dp[i-j] && (dict.find(s.substr(i-j, j)) != dict.end())) {
: dp[i] = true;
: break;
: }
|
n********e
发帖数: 41 | 5 多么漂亮的前缀字符串 DP 被你说成了 暴力解法。。。
substr(
"
【在 p***e 的大作中提到】
: 就我一外行来看，你这个不是dp呀。这个不就是O(n^2)的暴力解法嘛。不能因为变量名
: 字是dp,就叫dp算法吧。
:
: ><= i;="" j++)="" {="" :="" if="" (dp[i-j]="" &&="" (dict.find(s.substr(
: i-j,="" j))="" !="dict.end()))" {="" :="" dp[i]="true;" :="" break;="" :=""
: }="" :="" ...................="">
|
A*********t
发帖数: 64 | 6 暴力的是dfs。这个算是DP了，每个位置搜到都记录下来。
substr(
"
【在 p***e 的大作中提到】
: 就我一外行来看，你这个不是dp呀。这个不就是O(n^2)的暴力解法嘛。不能因为变量名
: 字是dp,就叫dp算法吧。
:
: ><= i;="" j++)="" {="" :="" if="" (dp[i-j]="" &&="" (dict.find(s.substr(
: i-j,="" j))="" !="dict.end()))" {="" :="" dp[i]="true;" :="" break;="" :=""
: }="" :="" ...................="">
|
s******d
发帖数: 424 | 7 bool wordBreak(string s, unordered_set &dict) {
vector f(s.size() + 1, false);
f[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
break;
}
}
}
return f[s.size()];
} |
s**x
发帖数: 7506 | 8 这道题总感觉应该把字典先建成trie.
网上搜索到的解法都是要试试几乎所有可能的子串，效率太差了。
至少应该先求出字典里最长单词的长度 I think. |
w******g
发帖数: 189 | |
p***e
发帖数: 111 | 10 我想错了，这个是dp. 而且复杂度是O(n^2 * s), s是字典长度。要想进一步优化，肯
定需要trie了。复杂度可以是O(n*s) 吧。
【在 A*********t 的大作中提到】
: 暴力的是dfs。这个算是DP了，每个位置搜到都记录下来。
:
: substr(
: "
|
s**x
发帖数: 7506 | 11
有了trie，复杂度应该是O(nW), where W is average of word length in the
dictionary.
假如我们忽略trie 的构建成本。
【在 p***e 的大作中提到】
: 我想错了，这个是dp. 而且复杂度是O(n^2 * s), s是字典长度。要想进一步优化，肯
: 定需要trie了。复杂度可以是O(n*s) 吧。
|
w******g
发帖数: 189 | 12 为什么有了trie，复杂度应该是O(nW)？
能不能贴个pseudo code? |
s**x
发帖数: 7506 | 13
有了trie，checking a substring is a prefix of any words become very easy,
just traverse the path in the trie.
for example， if no word begins with abc, you do not need to check if abcd，
abcde is in the dictionary or not.
when trie is not used, you have to lookup the dictionary for all substrings
starting a given position.
可以看看boggle puzzle 那题，那题不用trie 好像没法弄。
【在 w******g 的大作中提到】
: 为什么有了trie，复杂度应该是O(nW)？
: 能不能贴个pseudo code?
|
