【骨骼狗家】新鲜出炉的面经

lovemyisa · 2018-10-31 09:59:59

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

jianpanxia

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

jianpanxia

为什么没人讨论一下第二题呢 - -

一剑终情

jianpanxia 发表于 2018/11/01 03:27:59
为什么没人讨论一下第二题呢 - -

第二题lc原题，建个图dfs就好

lovemyisa

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

jianpanxia

lovemyisa 发表于 2018-11-1 04:31
为啥会完犊子？
Map 里面就是 a, 0
扫A的时候，第一个character的在map里面是0，第二个还是0，第三还是 ...

那A= “abababa”
B = “aba”
咋办。。

lovemyisa

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

jianpanxia

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

naomiaiziji

public int wordBreakIII(String A, String B) {
int N = A.length();
int[] f = new int[N];
for (int j = 0; j < N; j++) {
if (isSubsequence(B, A.substring(0, j+1))) {
f[j] = 1;
} else {
f[j] = Integer.MAX_VALUE;
for (int i = 0; i < j; i++) {
if (f[i] && isSubsequence(B, A.substring(i+1, j+1))) f[j] = Math.min(f[j], f[i] + 1);
}
}
}
return f[N-1];
}
private boolean isSubsequence(String B, String a) {
while (index != -1 && i < a.length()) {
index = B.indexOf(""+a.charAt(i++));
}
return index != -1 && i == a.length();
}

复制代码

用了一种保险的动态规划尝试做了下这道题，求指正。

josiexianli

naomiaiziji 发表于 2018-11-3 02:00
[mw_shl_code=java,true]public int wordBreakIII(String A, String B) {
int N = A.length();
int[] f ...

请问时间复杂度是是O（N^3）吗

【骨骼 狗家】新鲜出炉的面经