小朋友超级胆小怎么办，有什么办法呢？# 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:
相关阅读
旅行就是学习送给学校一年级小朋友的春节红包里装什么?家有一对双胞胎，怎么解决他们的睡觉问题？(转载)教育孩子最不可犯的七个致命错误３岁女娃受伤不愿告诉父母美国很多大学录取不要SAT了 (转载)有没有人转让《四五快读》？只认钱不认人的父母，偏偏被我赶上了！小朋友闹脾气问题不要刻意培养“听话的乖孩子”给爱哭的小孩吃治抑郁症的药，对吗？著名的亚斯伯格症女孩被射死溺爱害的我自己好惨这样才能进哈佛Freezing rain and snowBrains of Compulsive Video Gamers May Be 'Wired' Differentl去迪拜工作，带孩子去？？请学会善待“别人家的孩子”椭圆初中生的性行为过早 (转载)