a*********0
发帖数: 2727 | 1 1， 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB,考虑pattern是有序的。
就是Minimum Window Substring的有序版 |
a*********0
发帖数: 2727 | 2 int minWindowSubString(const string& s, const string& t)
{
unordered_map> umap;
size_t ns=s.size();
size_t nt=t.size();
for(size_t i=0;i
umap.emplace_back(s[i], i);
}
int min=INT_MAX;
while(1) {
int pre=-1;
size_t start=0;
size_t i=0;
for(;i
int newpre=-1;
list ls=umap.find(nt[i]);
while(!ls.empty()) {
if(pre>ls.front()){
ls.pop_front();
} else {
if(i==0) start=ls.front();
newpre=ls.front();
}
}
if(newpre==pre) break;
pre=newpre;
}
if(i!=nt) break;
if(min>pre-start+1) min=pre-start+1;
}
return min;
} |
h****3
发帖数: 89 | |
m*******n
发帖数: 47 | 4 你的time complexity 是多少? 3 个loop嵌套。。
比下面的暴力解好？O(n^2)
int solve(string str, string p) {
int ip = 0;
int min_l = INT_MAX;
for(int i=0;i
if (str[i]!=p[0]) continue;
for(int j=i;j
if (str[j]==p[ip]) {
ip++;
if (ip==p.length()) {
ip=0;
min_l = min(min_l, j-i+1);
break;
}
}
}
}
return min_l
} |
a*********0
发帖数: 2727 | 5 我的是O(nk)
【在 m*******n 的大作中提到】
: 你的time complexity 是多少? 3 个loop嵌套。。
: 比下面的暴力解好？O(n^2)
: int solve(string str, string p) {
: int ip = 0;
: int min_l = INT_MAX;
: for(int i=0;i: if (str[i]!=p[0]) continue;
: for(int j=i;j: if (str[j]==p[ip]) {
: ip++;
|
G*********e
发帖数: 56 | 6 显然用KMP算法呀。DFA version的KMP就可以搞定。线性时间，空间复杂度是pattern的
长度* the number of distinct characters in pattern。
【在 a*********0 的大作中提到】
: 1， 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版
|
l*****n
发帖数: 246 | 7 我觉得这题如果是电面题的话，暴力解法就可以了吧。。。 |
h****3
发帖数: 89 | |
b***e
发帖数: 1419 | 9 如果pattern里没有重复的话可以是O(n)。
【在 a*********0 的大作中提到】
: 我的是O(nk)
|
y******s
发帖数: 92 | 10 问个问题：如果pattern是ABC，那ABBC算match吗？
【在 a*********0 的大作中提到】
: 1， 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版
|
|
|
c******n
发帖数: 4965 | 11 他这个不是find string match. 要找subsequence
【在 G*********e 的大作中提到】
: 显然用KMP算法呀。DFA version的KMP就可以搞定。线性时间，空间复杂度是pattern的
: 长度* the number of distinct characters in pattern。
|
c******n
发帖数: 4965 | 12 yes
【在 y******s 的大作中提到】
: 问个问题：如果pattern是ABC，那ABBC算match吗？
|
c******n
发帖数: 4965 | 13 mine, O(N)
package actualseen.mitbbs;
import java.util.*;
/**
* find the shortest subsequence within a string that matches a pattern
*
* for example AooAooUooB contains the sequence AUB, starting from index 3
*
* @author
*
*/
public class ShortestSubsequenceContainingPattern {
public String find(String s, String p) {
char ss[] = s.toCharArray();
char pp[] = p.toCharArray();
int prefixStart[] = new int[pp.length];
List char2Prefix[] = new List[256];
for (int i = 0; i < pp.length; i++) {
if (char2Prefix[pp[i]] == null) {
char2Prefix[pp[i]] = new ArrayList();
}
char2Prefix[pp[i]].add(i);
prefixStart[i] = -1;
}
int best = Integer.MAX_VALUE;
int bestStart = 0;
for (int i = 0; i < ss.length; i++) {
char c = ss[i];
List prefixes = char2Prefix[c];
if (prefixes != null) { // matches SOME position in the pattern
for (int j = prefixes.size() - 1; j >= 0; j--) {
int prefix = prefixes.get(j);
if (prefix > 0) { // the matching char is not the first
in pattern, so we need to check previous prefixes
if (prefixStart[prefix - 1] >= 0) { // previous
prefix already found
prefixStart[prefix] = prefixStart[prefix - 1];
prefixStart[prefix - 1] = -1; //no need for
shorter prefix
if (prefix == pp.length - 1) {
if (i - prefixStart[prefix] + 1 < best) {
best = Math.min(best, i
- prefixStart[prefix] + 1);
bestStart = prefixStart[prefix];
}
}
}
} else {
prefixStart[0] = i;
}
}
}
}
return new String(ss, bestStart, best);
}
public static void main(String args[]) {
ShortestSubsequenceContainingPattern p = new
ShortestSubsequenceContainingPattern();
assert p.find("AxxBAU2B", "AUB").equals("AU2B");
assert p.find("xxxAxAyUxBAffffU2B", "AUB").equals("AyUxB");
}
}
【在 a*********0 的大作中提到】
: 1， 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
: substring，结果是AUB,考虑pattern是有序的。
: 就是Minimum Window Substring的有序版
|
j**7
发帖数: 143 | 14 public String window(String S, String P) {
HashMap> indexMap = new HashMap<
Character, LinkedList>();
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
LinkedList list = indexMap.get(c);
if (list == null) {
list = new LinkedList();
list.add(i);
indexMap.put(c, list);
} else {
list.add(i);
}
}
String minSubString = null;
int min = Integer.MAX_VALUE;
while (true) {
int prev = -1;
int first = -1;
for (int i = 0; i < P.length(); i++) {
char c = P.charAt(i);
LinkedList list = indexMap.get(c);
if (list == null) {
return null;
}
while (list.isEmpty() == false && list.getFirst() <= prev) {
list.removeFirst();
}
if (list.isEmpty()) {
return minSubString;
}
if (i == 0) {
first = list.removeFirst();
prev = first;
} else {
prev = list.getFirst();
}
}
if (prev - first + 1 < min) {
min = prev - first + 1;
minSubString = S.substring(first, prev + 1);
}
}
} |
j**7
发帖数: 143 | |
