f*******r
发帖数: 1086 | 1 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
这个题目是dp？
有知道的大侠给个思路，非常感谢！ |
r****o
发帖数: 1950 | |
y*c
发帖数: 904 | 3 DP is one approach. But it should take O(n^2)
opt(j) = maximum number of chars in C from a[0] to [j]
start(j) = largest i, st. a[i] to a[j] contains opt(j) chars in C
Then try to compute opt(j) from opt(j-1) and start(j-1).
You only need to start from start(j-1). If opt(j) is a new char, opt(j)=opt(
j-1)+1 (a hash or map needs to be maintained to store all chars in C that
have been seen), otherwise, update start(j) (e.g. if a[start(j-1)] = a[j],
etc.) This would take up to j. So at the end it ta |
s*********t
发帖数: 1663 | 4 汗，看走眼了
【在 r****o 的大作中提到】
: 这个是不是返回包含c1...ck的最大范围?
|
s********l
发帖数: 998 | 5 我也觉得是~~
【在 r****o 的大作中提到】
: 这个是不是返回包含c1...ck的最大范围?
|
g*****u
发帖数: 298 | 6 这个复杂度我觉得不能做到O(n)，因为还要看k
我觉得是O(nlogk)
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
|
d****n
发帖数: 233 | 7 Use hashtable, we can achieve O(n)
【在 g*****u 的大作中提到】
: 这个复杂度我觉得不能做到O(n)，因为还要看k
: 我觉得是O(nlogk)
|
f*******r
发帖数: 1086 | 8 能解释的详细点吗？谢谢了:)
【在 d****n 的大作中提到】
: Use hashtable, we can achieve O(n)
|
l*****a
发帖数: 14598 | 9 这个题昨天就讨论过
http://www.mitbbs.com/article_t/JobHunting/31586251.html
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
|
d****n
发帖数: 233 | 10 Here is the code in C#, please do let me know if you find any bug
// This program returns the shortest substring is src
// which contains all charactors in dest
// INT_MAX returned if no coverage found
static int MinimumCover(string src, string dst)
{
int minDist = int.MaxValue;
Hashtable ht = new Hashtable();
ArrayList al = new ArrayList();
foreach (char c in dst)
{
ht.Add(c,1);
【在 f*******r 的大作中提到】
: 能解释的详细点吗？谢谢了:)
|
|
|
d****n
发帖数: 233 | 11 Forgot one small class:
class charPos {
public charPos(int pos, char ch)
{
m_ch=ch;
m_pos=pos;
}
public char m_ch;
public int m_pos;
};
【在 d****n 的大作中提到】
: Here is the code in C#, please do let me know if you find any bug
: // This program returns the shortest substring is src
: // which contains all charactors in dest
: // INT_MAX returned if no coverage found
: static int MinimumCover(string src, string dst)
: {
: int minDist = int.MaxValue;
: Hashtable ht = new Hashtable();
: ArrayList al = new ArrayList();
: foreach (char c in dst)
|
r****o
发帖数: 1950 | 12 能不能讲讲思路啊，这个复杂度好像不是O(n)，for里面还有while.
【在 d****n 的大作中提到】
: Here is the code in C#, please do let me know if you find any bug
: // This program returns the shortest substring is src
: // which contains all charactors in dest
: // INT_MAX returned if no coverage found
: static int MinimumCover(string src, string dst)
: {
: int minDist = int.MaxValue;
: Hashtable ht = new Hashtable();
: ArrayList al = new ArrayList();
: foreach (char c in dst)
|
l*****a
发帖数: 14598 | 13 while是针对保存match状态的hashtabl而言。
对于原字符串，就是一个O（n）的扫描
【在 r****o 的大作中提到】
: 能不能讲讲思路啊，这个复杂度好像不是O(n)，for里面还有while.
|
s*********t
发帖数: 1663 | 14 a = "what the hell is this"
k = ('e','h','s')
def longestSubString(a, k):
n=len(a)
dp = {}
dp[(0,0)] = {}
for j in k:
if a[0]==j:
dp[(0,0)][j] = 1
else:
dp[(0,0)][j] = 0
x=0;y=0;minlength = n+1;
while y
## print dp[(x,y)], a[x:y+1]
if not (0 in dp[(x,y)].values()):
"""found substr"""
if y-x+1 < minlength:
"""update minlength if necessary"""
minlength =
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
|
s*********t
发帖数: 1663 | 15 思路见注释
【在 s*********t 的大作中提到】
: a = "what the hell is this"
: k = ('e','h','s')
: def longestSubString(a, k):
: n=len(a)
: dp = {}
: dp[(0,0)] = {}
: for j in k:
: if a[0]==j:
: dp[(0,0)][j] = 1
: else:
|
