I*I
发帖数: 618 | 1 如何找到长字符串中的一个最短子串，满足子串中按顺序包括了另一个字符串中的所有
字符。
真心复杂啊。。
如果不按顺序好办，按照顺序就太纠结了。。
多谢 |
f****0
发帖数: 151 | 2 A = "acbc"
B = "abc"
这个算按顺序吗？ |
p*****2
发帖数: 21240 | |
I*I
发帖数: 618 | 4 就是想知道DP怎么解啊？特别是子串比较大的时候？
【在 p*****2 的大作中提到】
: DFS玩腻了。这题用DP解吧。
|
p*****2
发帖数: 21240 | 5
多大？
【在 I*I 的大作中提到】
: 就是想知道DP怎么解啊？特别是子串比较大的时候？
|
I*I
发帖数: 618 | 6 这时候只有A才是算按顺序包含B，而A的头三个字母不算按顺序包含B
【在 f****0 的大作中提到】
: A = "acbc"
: B = "abc"
: 这个算按顺序吗？
|
Z*****Z
发帖数: 723 | 7 挺有意思的小题儿。
假设主串长度为M，模式串长度为N，一般N << M.
brute force的算法就是从主串的每一位开始找，worst case O（M2）
给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
的。
还没想到O（M+N）的算法。期待牛人解惑。。。
【在 I*I 的大作中提到】
: 这时候只有A才是算按顺序包含B，而A的头三个字母不算按顺序包含B
|
p*****2
发帖数: 21240 | 8
给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
的。
这个具体你准备怎么搞？感觉O(MN)应该就可以了。
【在 Z*****Z 的大作中提到】
: 挺有意思的小题儿。
: 假设主串长度为M，模式串长度为N，一般N << M.
: brute force的算法就是从主串的每一位开始找，worst case O（M2）
: 给模式串里面的每个位置用一个指针记录上次搜索到的位置，很容易就改进成O（MN）
: 的。
: 还没想到O（M+N）的算法。期待牛人解惑。。。
|
g*********e
发帖数: 14401 | 9 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; |
Z*****Z
发帖数: 723 | 10 模式串里面有可能有重复字符，比如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{
|
|
|
p*****2
发帖数: 21240 | 11 假设模式串target长度为N，弄N个指针，每次循环:
第一个指针在主串中找到下一个target[0]的位置，
第二个指针在主串中找到大于第一个指针的target[1]的位置
第三个指针在主串中找到大于第二个指针的target[2]的位置
。。。
这样就找到了一个解，记录之。
找一个解的复杂度就是M*N了吧？
你要是找全不成了M^2*N了？
【在 Z*****Z 的大作中提到】
: 模式串里面有可能有重复字符，比如abcabc，你不能每次看见a就open一个candidate而
: 不做search吧。
|
Z*****Z
发帖数: 723 | 12
找第一个解有可能是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
发帖数: 21240 | 13
明白了。这样应该可以。
【在 Z*****Z 的大作中提到】
:
: 找第一个解有可能是M*N的，但是可以优化成M。最重要的是，整个的复杂度是M*N的，
: 因为N个指针，每个指针从头到尾扫了M一遍。
|
j********e
发帖数: 1192 | 14 这题难度不是Longest Common Sequence的变种么？
DP的话，如果LCS(X[i-1],Y[j])和LCS(X[i], Y[j-1])一样的话，需要选择
上一个match的字符最近的那一个。
【在 I*I 的大作中提到】
: 如何找到长字符串中的一个最短子串，满足子串中按顺序包括了另一个字符串中的所有
: 字符。
: 真心复杂啊。。
: 如果不按顺序好办，按照顺序就太纠结了。。
: 多谢
|
Z*****Z
发帖数: 723 | 15 貌似LCS的空间复杂度是O(M*N)的？
【在 j********e 的大作中提到】
: 这题难度不是Longest Common Sequence的变种么？
: DP的话，如果LCS(X[i-1],Y[j])和LCS(X[i], Y[j-1])一样的话，需要选择
: 上一个match的字符最近的那一个。
|
p*****2
发帖数: 21240 | 16
不能优化空间吗？
【在 Z*****Z 的大作中提到】
: 貌似LCS的空间复杂度是O(M*N)的？
|
Z*****Z
发帖数: 723 | 17 对，能空间优化。
但是LCS，那个DP表里存的是A[i]和B[j]之间最长的CS，我还没想清楚在这个问题里那个
DP表长什么样
【在 p*****2 的大作中提到】
:
: 不能优化空间吗？
|
p*****2
发帖数: 21240 | 18
那个
假设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
发帖数: 723 | 19 最后的解在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
发帖数: 21240 | 20
dp[*][0]吧。按照题意。
因为最短的有可能在任意位置开始。而需要cover整个word
【在 Z*****Z 的大作中提到】
: 最后的解在dp[0][*]里面找?还是在哪儿？
|
|
|
Z*****Z
发帖数: 723 | 21 对的对的，二爷精准，一针见血
【在 p*****2 的大作中提到】
:
: dp[*][0]吧。按照题意。
: 因为最短的有可能在任意位置开始。而需要cover整个word
|
p*****2
发帖数: 21240 | 22
你这是啥头像呀？跟你名字不符呀。
【在 Z*****Z 的大作中提到】
: 对的对的，二爷精准，一针见血
|
Z*****Z
发帖数: 723 | 23 呵呵，看着看着就习惯了
【在 p*****2 的大作中提到】
:
: 你这是啥头像呀？跟你名字不符呀。
|
p*****2
发帖数: 21240 | 24 白芷，我写了一个，你看看有没有问题。空间可以优化到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;
} |
Z*****Z
发帖数: 723 | 25 二爷，看不太懂 :(
写了两个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
发帖数: 21240 | 26
我刚才有个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
发帖数: 21240 | |
Z*****Z
发帖数: 723 | 28 zan!
【在 p*****2 的大作中提到】
: 试了一下，输出试
: 2134
: 102312
|
p*****2
发帖数: 21240 | 29
白芷帮我看看这段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]
min=dp[i][0]
ans=sentence[i:i+min]
return ans
print find("12314102312","12312")
print find("992134923034","234")
【在 Z*****Z 的大作中提到】
: zan!
|
Z*****Z
发帖数: 723 | 30 二爷要征服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
:
|
|
|
p*****2
发帖数: 21240 | 31
得节
我觉得可以优化到短字符串的长度吧？
因为for i,j, 我们只需要i+1,j+1
所以可以存短字符串的长度的cache就可以了吧？循环要改一下了。
【在 Z*****Z 的大作中提到】
: 二爷要征服Python啦，太赞了
: 我先re一个再仔细看看。
: 不过这题后来想了一下，DP空间最优化也得是长字符串的长度吧。不如搞N个指针来得节
: 省。
|
p*****2
发帖数: 21240 | 32 正在学习python，很不喜欢。还得请你老多指教呀 |
Z*****Z
发帖数: 723 | 33 我在读程序的时候能看出来，呵呵
其实我也是新手，大家一起学习进步吧
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
|
Z*****Z
发帖数: 723 | 34 我只是把我知道的可能的不同的写法在这里改一下，改过了不一定好，只是提供另外一
种思路。其实我现在还远没有达到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
发帖数: 723 | 35 对，又晕菜了。
【在 p*****2 的大作中提到】
: 正在学习python，很不喜欢。还得请你老多指教呀
|
p*****2
发帖数: 21240 | 36
我的意思是很不习惯。呵呵。感觉挺别扭的。
【在 Z*****Z 的大作中提到】
: 我在读程序的时候能看出来，呵呵
: 其实我也是新手，大家一起学习进步吧
|
p*****2
发帖数: 21240 | 37
靠。你太牛了。这得够我学一阵子的。
【在 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:
|
