Bloomberg面试题 分析

问大家一道Bloomberg面试题， 给一个string (''ap

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

间复杂度是多少？我用递归做的， 但分析不出复杂度

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

119018682 发表于 2017-9-19 02:47
请问楼主是java选手么

是Java选手， 面个实习第一题就是word break, 今天才知道， 在我写两遍做出来后， 烙印送上奇招， BST to Double Linked List, 心满意足地将我挂掉

大家不要用set去递归啊， 因为有说set里有 百万的string

请参考 利口 word break, 用dp 做

补充内容 (2017-9-19 02:31):
if( input[i...j] belongs in dictionary) T[i][j] = i
else{
     T[i][j] = k if T[i][k-1] != -1 && T[k][j] != -1

seannaes 发表于 2017-9-19 02:28
请参考 利口 word break, 用dp 做

我会做，但我问的是 时空复杂度

wxl3691 发表于 2017-9-19 02:29
我会做，但我问的是 时空复杂度

二维dp, 都是O(N^2)

seannaes 发表于 2017-9-19 02:33
二维dp, 都是O(N^2)

我没用什么DP，就DFS， 时间复杂度答 O(N^2), 烙印当场说我是错的， 说比O(N^2) 高

wxl3691 发表于 2017-9-19 02:36
我没用什么DP，就DFS， 时间复杂度答 O(N^2), 烙印当场说我是错的， 说比O(N^2) 高

DFS 的话, 时间O(2^n)

wxl3691 发表于 2017-9-19 02:36
我没用什么DP，就DFS， 时间复杂度答 O(N^2), 烙印当场说我是错的， 说比O(N^2) 高

请问楼主是java选手么

seannaes 发表于 2017-9-19 02:47
DFS 的话, 时间O(2^n)

能解释下吗，我遇到递归， DFS就无法分析了， 为什么是2啊？