小朋友超级胆小怎么办，有什么办法呢？# Parenting - 为人父母
I*I
1 楼
如何找到长字符串中的一个最短子串，满足子串中按顺序包括了另一个字符串中的所有
字符。
真心复杂啊。。
如果不按顺序好办，按照顺序就太纠结了。。
多谢
字符。
真心复杂啊。。
如果不按顺序好办，按照顺序就太纠结了。。
多谢
m*i
2 楼
快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
pirate不敢看，最近发展到curious George也不敢看。
不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
。完全没有恐怖的地方啊。
平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
么办法让他勇敢一些？
自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
pirate不敢看，最近发展到curious George也不敢看。
不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
。完全没有恐怖的地方啊。
平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
么办法让他勇敢一些？
f*0
3 楼
A = "acbc"
B = "abc"
这个算按顺序吗？
B = "abc"
这个算按顺序吗？
w*t
4 楼
为啥要看？你说的这些我儿子全部没看过，土啊
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
p*2
5 楼
DFS玩腻了。这题用DP解吧。
w*t
6 楼
过一年，孩子变化很大的
我儿子以前死活不肯喝水，只能喂各种果汁，现在除了水，什么都不喝，天天自己倒水喝
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
我儿子以前死活不肯喝水，只能喂各种果汁，现在除了水，什么都不喝，天天自己倒水喝
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
I*I
7 楼
就是想知道DP怎么解啊？特别是子串比较大的时候？
【在 p*****2 的大作中提到】
: DFS玩腻了。这题用DP解吧。
【在 p*****2 的大作中提到】
: DFS玩腻了。这题用DP解吧。
R*i
8 楼
大点会好。不敢看就先不看吧，总有不怕的。我女儿两岁半的时候看curious George和
finding nemo也害怕。看madagascar吓哭了，我一直都没明白被什么吓的。后来开始和
小朋友一起看各种动画片。现在我们得限制她看。
finding nemo也害怕。看madagascar吓哭了，我一直都没明白被什么吓的。后来开始和
小朋友一起看各种动画片。现在我们得限制她看。
p*2
9 楼
多大？
【在 I*I 的大作中提到】
: 就是想知道DP怎么解啊？特别是子串比较大的时候？
b*e
10 楼
宝宝好可爱
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
I*I
11 楼
这时候只有A才是算按顺序包含B，而A的头三个字母不算按顺序包含B
【在 f****0 的大作中提到】
: A = "acbc"
: B = "abc"
: 这个算按顺序吗？
【在 f****0 的大作中提到】
: A = "acbc"
: B = "abc"
: 这个算按顺序吗？
s*j
12 楼
"最近发展到curious George也不敢看"
看来只剩下 peep and the big wide world 可以试一试了.
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
看来只剩下 peep and the big wide world 可以试一试了.
【在 m****i 的大作中提到】
: 快3岁的孩子，特别胆子小。很小的时候看find nemo，nemo妈妈被吃掉他吓哭了。
: 自那以后，都快一年，还是超级胆小。Princess Sofia不敢看，Jack the neverland
: pirate不敢看，最近发展到curious George也不敢看。
: 不但不敢看这些节目，连书都害怕。昨天给哥哥讲The little blue truck,他给吓哭了
: 。完全没有恐怖的地方啊。
: 平时特别sweet,友好爱撒娇，就是这个胆子小。这将来上学story time怎么办啊？有什
: 么办法让他勇敢一些？
Z*Z
13 楼
挺有意思的小题儿。
假设主串长度为M，模式串长度为N，一般N << M.
brute force的算法就是从主串的每一位开始找，worst case O（M2）
给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
的。
还没想到O（M+N）的算法。期待牛人解惑。。。
【在 I*I 的大作中提到】
: 这时候只有A才是算按顺序包含B，而A的头三个字母不算按顺序包含B
假设主串长度为M，模式串长度为N，一般N << M.
brute force的算法就是从主串的每一位开始找，worst case O（M2）
给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
的。
还没想到O（M+N）的算法。期待牛人解惑。。。
【在 I*I 的大作中提到】
: 这时候只有A才是算按顺序包含B，而A的头三个字母不算按顺序包含B
f*e
14 楼
别说你孩子了，我听着都害怕！！要允许胆小的人存在！！
p*2
15 楼
给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
的。
这个具体你准备怎么搞？感觉O(MN)应该就可以了。
【在 Z*****Z 的大作中提到】
: 挺有意思的小题儿。
: 假设主串长度为M，模式串长度为N，一般N << M.
: brute force的算法就是从主串的每一位开始找，worst case O（M2）
: 给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
: 的。
: 还没想到O（M+N）的算法。期待牛人解惑。。。
g*e
16 楼
struct candidate{
start position;
current position;
int length;
}
扫一遍长字符串M,
if(M[i]==N[0]) open a new candidate, candidate.startPosition=i; candidate.
currentPosition=0;
else{
for each candidate{
if(M[i]==N[candidate.currentPosition+1])
candidate.currentPosition++;
if(candidate.currentPosition==n-1)
candidate.length=i-candidate.startPosition;
}
find the candidate with shortest length;
start position;
current position;
int length;
}
扫一遍长字符串M,
if(M[i]==N[0]) open a new candidate, candidate.startPosition=i; candidate.
currentPosition=0;
else{
for each candidate{
if(M[i]==N[candidate.currentPosition+1])
candidate.currentPosition++;
if(candidate.currentPosition==n-1)
candidate.length=i-candidate.startPosition;
}
find the candidate with shortest length;
Z*Z
17 楼
模式串里面有可能有重复字符，比如abcabc，你不能每次看见a就open一个candidate而
不做search吧。
【在 g*********e 的大作中提到】
: struct candidate{
: start position;
: current position;
: int length;
: }
: 扫一遍长字符串M,
: if(M[i]==N[0]) open a new candidate, candidate.startPosition=i; candidate.
: currentPosition=0;
: else{
: for each candidate{
不做search吧。
【在 g*********e 的大作中提到】
: struct candidate{
: start position;
: current position;
: int length;
: }
: 扫一遍长字符串M,
: if(M[i]==N[0]) open a new candidate, candidate.startPosition=i; candidate.
: currentPosition=0;
: else{
: for each candidate{
p*2
18 楼
假设模式串target长度为N，弄N个指针，每次循环:
第一个指针在主串中找到下一个target[0]的位置，
第二个指针在主串中找到大于第一个指针的target[1]的位置
第三个指针在主串中找到大于第二个指针的target[2]的位置
。。。
这样就找到了一个解，记录之。
找一个解的复杂度就是M*N了吧？
你要是找全不成了M^2*N了？
【在 Z*****Z 的大作中提到】
: 模式串里面有可能有重复字符，比如abcabc，你不能每次看见a就open一个candidate而
: 不做search吧。
第一个指针在主串中找到下一个target[0]的位置，
第二个指针在主串中找到大于第一个指针的target[1]的位置
第三个指针在主串中找到大于第二个指针的target[2]的位置
。。。
这样就找到了一个解，记录之。
找一个解的复杂度就是M*N了吧？
你要是找全不成了M^2*N了？
【在 Z*****Z 的大作中提到】
: 模式串里面有可能有重复字符，比如abcabc，你不能每次看见a就open一个candidate而
: 不做search吧。
Z*Z
19 楼
找第一个解有可能是M*N的，但是可以优化成M。最重要的是，整个的复杂度是M*N的，
因为N个指针，每个指针从头到尾扫了M一遍。
【在 p*****2 的大作中提到】
: 假设模式串target长度为N，弄N个指针，每次循环:
: 第一个指针在主串中找到下一个target[0]的位置，
: 第二个指针在主串中找到大于第一个指针的target[1]的位置
: 第三个指针在主串中找到大于第二个指针的target[2]的位置
: 。。。
: 这样就找到了一个解，记录之。
: 找一个解的复杂度就是M*N了吧？
: 你要是找全不成了M^2*N了？
p*2
20 楼
明白了。这样应该可以。
【在 Z*****Z 的大作中提到】
:
: 找第一个解有可能是M*N的，但是可以优化成M。最重要的是，整个的复杂度是M*N的，
: 因为N个指针，每个指针从头到尾扫了M一遍。
j*e
21 楼
这题难度不是Longest Common Sequence的变种么？
DP的话，如果LCS(X[i-1],Y[j])和LCS(X[i], Y[j-1])一样的话，需要选择
上一个match的字符最近的那一个。
【在 I*I 的大作中提到】
: 如何找到长字符串中的一个最短子串，满足子串中按顺序包括了另一个字符串中的所有
: 字符。
: 真心复杂啊。。
: 如果不按顺序好办，按照顺序就太纠结了。。
: 多谢
DP的话，如果LCS(X[i-1],Y[j])和LCS(X[i], Y[j-1])一样的话，需要选择
上一个match的字符最近的那一个。
【在 I*I 的大作中提到】
: 如何找到长字符串中的一个最短子串，满足子串中按顺序包括了另一个字符串中的所有
: 字符。
: 真心复杂啊。。
: 如果不按顺序好办，按照顺序就太纠结了。。
: 多谢
Z*Z
22 楼
貌似LCS的空间复杂度是O(M*N)的？
【在 j********e 的大作中提到】
: 这题难度不是Longest Common Sequence的变种么？
: DP的话，如果LCS(X[i-1],Y[j])和LCS(X[i], Y[j-1])一样的话，需要选择
: 上一个match的字符最近的那一个。
【在 j********e 的大作中提到】
: 这题难度不是Longest Common Sequence的变种么？
: DP的话，如果LCS(X[i-1],Y[j])和LCS(X[i], Y[j-1])一样的话，需要选择
: 上一个match的字符最近的那一个。
p*2
23 楼
不能优化空间吗？
【在 Z*****Z 的大作中提到】
: 貌似LCS的空间复杂度是O(M*N)的？
Z*Z
24 楼
对，能空间优化。
但是LCS，那个DP表里存的是A[i]和B[j]之间最长的CS，我还没想清楚在这个问题里那个
DP表长什么样
【在 p*****2 的大作中提到】
:
: 不能优化空间吗？
但是LCS，那个DP表里存的是A[i]和B[j]之间最长的CS，我还没想清楚在这个问题里那个
DP表长什么样
【在 p*****2 的大作中提到】
:
: 不能优化空间吗？
p*2
25 楼
那个
假设str， word 是input
我觉得dp[i][j]
代表从str i的位置往后，包含word (j-word.length()-1) 的最短长度
if(str[i]==word[j])
dp[i][j]=1+dp[i+1][j+1]
else
dp[i][j]=1+dp[i+1][j]
【在 Z*****Z 的大作中提到】
: 对，能空间优化。
: 但是LCS，那个DP表里存的是A[i]和B[j]之间最长的CS，我还没想清楚在这个问题里那个
: DP表长什么样
Z*Z
26 楼
最后的解在dp[0][*]里面找?还是在哪儿？
【在 p*****2 的大作中提到】
:
: 那个
: 假设str， word 是input
: 我觉得dp[i][j]
: 代表从str i的位置往后，包含word (j-word.length()-1) 的最短长度
: if(str[i]==word[j])
: dp[i][j]=1+dp[i+1][j+1]
: else
: dp[i][j]=1+dp[i+1][j]
【在 p*****2 的大作中提到】
:
: 那个
: 假设str， word 是input
: 我觉得dp[i][j]
: 代表从str i的位置往后，包含word (j-word.length()-1) 的最短长度
: if(str[i]==word[j])
: dp[i][j]=1+dp[i+1][j+1]
: else
: dp[i][j]=1+dp[i+1][j]
p*2
27 楼
dp[*][0]吧。按照题意。
因为最短的有可能在任意位置开始。而需要cover整个word
【在 Z*****Z 的大作中提到】
: 最后的解在dp[0][*]里面找?还是在哪儿？
Z*Z
28 楼
对的对的，二爷精准，一针见血
【在 p*****2 的大作中提到】
:
: dp[*][0]吧。按照题意。
: 因为最短的有可能在任意位置开始。而需要cover整个word
【在 p*****2 的大作中提到】
:
: dp[*][0]吧。按照题意。
: 因为最短的有可能在任意位置开始。而需要cover整个word
p*2
29 楼
你这是啥头像呀？跟你名字不符呀。
【在 Z*****Z 的大作中提到】
: 对的对的，二爷精准，一针见血
Z*Z
30 楼
呵呵，看着看着就习惯了
【在 p*****2 的大作中提到】
:
: 你这是啥头像呀？跟你名字不符呀。
【在 p*****2 的大作中提到】
:
: 你这是啥头像呀？跟你名字不符呀。
p*2
31 楼
白芷，我写了一个，你看看有没有问题。空间可以优化到2*m， 后边找最短的也可以一
并做了。不过这个主要是实现这个思路，没有优化。
String min(String str, String word)
{
int n = str.length();
int m = word.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++)
dp[i][m] = 0;
for (int j = 0; j < m; j++)
dp[n][j] = n + 1;
for (int i = n - 1; i >= 0; i--)
for (int j = m - 1; j >= 0; j--)
{
if (str.charAt(i) == word.charAt(j))
{
dp[i][j] = 1 + dp[i + 1][j + 1];
}
else
{
dp[i][j] = 1 + dp[i + 1][j];
}
}
String ans = "none";
int min = n + 1;
for (int i = 0; i < n; i++)
{
if (dp[i][0] < min)
{
min = dp[i][0];
ans = str.substring(i, i+dp[i][0]);
}
}
return ans;
}
并做了。不过这个主要是实现这个思路，没有优化。
String min(String str, String word)
{
int n = str.length();
int m = word.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++)
dp[i][m] = 0;
for (int j = 0; j < m; j++)
dp[n][j] = n + 1;
for (int i = n - 1; i >= 0; i--)
for (int j = m - 1; j >= 0; j--)
{
if (str.charAt(i) == word.charAt(j))
{
dp[i][j] = 1 + dp[i + 1][j + 1];
}
else
{
dp[i][j] = 1 + dp[i + 1][j];
}
}
String ans = "none";
int min = n + 1;
for (int i = 0; i < n; i++)
{
if (dp[i][0] < min)
{
min = dp[i][0];
ans = str.substring(i, i+dp[i][0]);
}
}
return ans;
}
Z*Z
32 楼
二爷，看不太懂 :(
写了两个testcase您看看？
public class SearchSequence {
static String min(String str, String word) {
int n = str.length();
int m = word.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++)
dp[i][m] = 0;
for (int j = 0; j < m; j++)
dp[n][j] = n + 1;
for (int i = n - 1; i >= 0; i--)
for (int j = m - 1; j >= 0; j--) {
if (str.charAt(i) == word.charAt(j)) {
dp[i][j] = 1 + dp[i + 1][j + 1];
} else {
dp[i][j] = 1 + dp[i + 1][j];
}
}
String ans = "none";
int min = n + 1;
for (int i = 0; i < n; i++) {
if (dp[i][0] < min) {
min = dp[i][0];
ans = str.substring(i, dp[i][0]);
}
}
return ans;
}
public static void main(String[] args) {
String str = "992134923034";
String word = "234";
System.out.println(min(str,word));
str = "12314102312";
word = "12312";
System.out.println(min(str,word));
}
}
【在 p*****2 的大作中提到】
: 白芷，我写了一个，你看看有没有问题。空间可以优化到2*m， 后边找最短的也可以一
: 并做了。不过这个主要是实现这个思路，没有优化。
: String min(String str, String word)
: {
: int n = str.length();
: int m = word.length();
: int[][] dp = new int[n + 1][m + 1];
: for (int i = 0; i <= n; i++)
: dp[i][m] = 0;
: for (int j = 0; j < m; j++)
写了两个testcase您看看？
public class SearchSequence {
static String min(String str, String word) {
int n = str.length();
int m = word.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++)
dp[i][m] = 0;
for (int j = 0; j < m; j++)
dp[n][j] = n + 1;
for (int i = n - 1; i >= 0; i--)
for (int j = m - 1; j >= 0; j--) {
if (str.charAt(i) == word.charAt(j)) {
dp[i][j] = 1 + dp[i + 1][j + 1];
} else {
dp[i][j] = 1 + dp[i + 1][j];
}
}
String ans = "none";
int min = n + 1;
for (int i = 0; i < n; i++) {
if (dp[i][0] < min) {
min = dp[i][0];
ans = str.substring(i, dp[i][0]);
}
}
return ans;
}
public static void main(String[] args) {
String str = "992134923034";
String word = "234";
System.out.println(min(str,word));
str = "12314102312";
word = "12312";
System.out.println(min(str,word));
}
}
【在 p*****2 的大作中提到】
: 白芷，我写了一个，你看看有没有问题。空间可以优化到2*m， 后边找最短的也可以一
: 并做了。不过这个主要是实现这个思路，没有优化。
: String min(String str, String word)
: {
: int n = str.length();
: int m = word.length();
: int[][] dp = new int[n + 1][m + 1];
: for (int i = 0; i <= n; i++)
: dp[i][m] = 0;
: for (int j = 0; j < m; j++)
p*2
33 楼
我刚才有个bug，刚fix了。我看你用的我老的code。
【在 Z*****Z 的大作中提到】
: 二爷，看不太懂 :(
: 写了两个testcase您看看？
: public class SearchSequence {
: static String min(String str, String word) {
: int n = str.length();
: int m = word.length();
: int[][] dp = new int[n + 1][m + 1];
: for (int i = 0; i <= n; i++)
: dp[i][m] = 0;
: for (int j = 0; j < m; j++)
p*2
34 楼
试了一下，输出试
2134
102312
2134
102312
Z*Z
35 楼
zan!
【在 p*****2 的大作中提到】
: 试了一下，输出试
: 2134
: 102312
【在 p*****2 的大作中提到】
: 试了一下，输出试
: 2134
: 102312
p*2
36 楼
白芷帮我看看这段code好吗？指点我一下。
def find(sentence, word):
n=len(sentence)
m=len(word)
dp=[[0 for x in xrange(m+1)] for x in xrange(n+1)]
for i in xrange(n+1):
dp[i][m]=0
for j in xrange(m):
dp[n][j]=n+1
for i in xrange(n-1,-1,-1):
for j in xrange(m-1,-1,-1):
if sentence[i]==word[j]:
dp[i][j]=1+dp[i+1][j+1]
else:
dp[i][j]=1+dp[i+1][j]
ans="none"
min=n+1
for i in xrange(n):
if dp[i][0]
ans=sentence[i:i+min]
return ans
print find("12314102312","12312")
print find("992134923034","234")
【在 Z*****Z 的大作中提到】
: zan!
Z*Z
37 楼
二爷要征服Python啦，太赞了
我先re一个再仔细看看。
不过这题后来想了一下，DP空间最优化也得是长字符串的长度吧。不如搞N个指针来得节
省。
【在 p*****2 的大作中提到】
:
: 白芷帮我看看这段code好吗？指点我一下。
: def find(sentence, word):
: n=len(sentence)
: m=len(word)
: dp=[[0 for x in xrange(m+1)] for x in xrange(n+1)]
:
: for i in xrange(n+1):
: dp[i][m]=0
:
我先re一个再仔细看看。
不过这题后来想了一下，DP空间最优化也得是长字符串的长度吧。不如搞N个指针来得节
省。
【在 p*****2 的大作中提到】
:
: 白芷帮我看看这段code好吗？指点我一下。
: def find(sentence, word):
: n=len(sentence)
: m=len(word)
: dp=[[0 for x in xrange(m+1)] for x in xrange(n+1)]
:
: for i in xrange(n+1):
: dp[i][m]=0
:
p*2
38 楼
得节
我觉得可以优化到短字符串的长度吧？
因为for i,j, 我们只需要i+1,j+1
所以可以存短字符串的长度的cache就可以了吧？循环要改一下了。
【在 Z*****Z 的大作中提到】
: 二爷要征服Python啦，太赞了
: 我先re一个再仔细看看。
: 不过这题后来想了一下，DP空间最优化也得是长字符串的长度吧。不如搞N个指针来得节
: 省。
p*2
39 楼
正在学习python，很不喜欢。还得请你老多指教呀
Z*Z
40 楼
我在读程序的时候能看出来，呵呵
其实我也是新手，大家一起学习进步吧
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
其实我也是新手，大家一起学习进步吧
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
Z*Z
41 楼
我只是把我知道的可能的不同的写法在这里改一下，改过了不一定好，只是提供另外一
种思路。其实我现在还远没有达到thinking in python那步
from itertools import product
dp=[[0] * (m+1) for _ in xrange(n+1)]
dp[n] = [n+1] * (m+1)
for i,j in product(xrange(n-1,-1,-1), xrange(m-1,-1,-1)):
li = [dp[i][0] for i in xrange(n)]
minLen = min(li)
if minLen < n+1:
i = li.index(minLen)
ans=sentence[i:i+minLen]
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
种思路。其实我现在还远没有达到thinking in python那步
from itertools import product
dp=[[0] * (m+1) for _ in xrange(n+1)]
dp[n] = [n+1] * (m+1)
for i,j in product(xrange(n-1,-1,-1), xrange(m-1,-1,-1)):
li = [dp[i][0] for i in xrange(n)]
minLen = min(li)
if minLen < n+1:
i = li.index(minLen)
ans=sentence[i:i+minLen]
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
Z*Z
42 楼
对，又晕菜了。
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
p*2
43 楼
我的意思是很不习惯。呵呵。感觉挺别扭的。
【在 Z*****Z 的大作中提到】
: 我在读程序的时候能看出来，呵呵
: 其实我也是新手，大家一起学习进步吧
p*2
44 楼
靠。你太牛了。这得够我学一阵子的。
【在 Z*****Z 的大作中提到】
: 我只是把我知道的可能的不同的写法在这里改一下，改过了不一定好，只是提供另外一
: 种思路。其实我现在还远没有达到thinking in python那步
:
: from itertools import product
: dp=[[0] * (m+1) for _ in xrange(n+1)]
: dp[n] = [n+1] * (m+1)
: for i,j in product(xrange(n-1,-1,-1), xrange(m-1,-1,-1)):
: li = [dp[i][0] for i in xrange(n)]
: minLen = min(li)
: if minLen < n+1:
相关阅读
高档小区素质最差的就是不喜欢音乐的人最爱买摆设琴这个极品楼主跟当地房产经纪人合伙的吧父母的语气影响孩子一生(图)10岁男娃过生日，带啥礼物比较好Re: 邻居探亲老人打我家孩子和一个印度小女孩【请问】左利手需要纠正吗？长大有可能换右手吗？看的真累啊有人家有bunk bed吗？中文 Immersion Program 班级奖励（图）四岁孩子测谎实验儿子的笑话关于探亲老人打小孩事件2015年1月24日大芝加哥地区围棋数学研讨会纵容自己小孩的父母最欠揍了critical thinking vs 批判式思考4 years old, frequent pee accident in preschool买一堆数学书的家长通常数学不行，但落灰在行。请问夹住小朋友手套和衣服的那种夹子那里有卖？ (转载)一帮数典忘宗的孙子