b******g
发帖数: 1721 | 1 input:
string 1: “A B C”
string 2: “BKKAFFCFBJCAHHBC”
output:
BJCA
目标：
要发现string2里面最短的substring，这个string包含所有的string1里面的字符。
有什么好的算法？ |
b******g
发帖数: 1721 | 2 idea：
1.扫一遍string2，把不在string1的字符去掉
2.再扫一遍updated string2，看连起来的substring是否包含string1的所有字符。如
果是，计算长度。保留最短的
第二步有个optimization是一旦出现重复字符，自动取消先前那个，重新算substring。
复杂度是 O（n＊m）where n是string2的长度，m是string1的长度。可以用hash表来优
化判断是否出现。所以复杂度可以是O（n） |
f********4
发帖数: 988 | |
r*******e
发帖数: 7583 | 4 第一步没有必要，也不能去掉
题目要求的是返回符合条件的substring，去掉就破坏原字符串了
substring。
【在 b******g 的大作中提到】
: idea：
: 1.扫一遍string2，把不在string1的字符去掉
: 2.再扫一遍updated string2，看连起来的substring是否包含string1的所有字符。如
: 果是，计算长度。保留最短的
: 第二步有个optimization是一旦出现重复字符，自动取消先前那个，重新算substring。
: 复杂度是 O（n＊m）where n是string2的长度，m是string1的长度。可以用hash表来优
: 化判断是否出现。所以复杂度可以是O（n）
|
b******7
发帖数: 92 | 5 这就是那个有名的两指针蠕虫算法，p0,p1两指针，p1在前，p1加到包含所有string 1
的时候，p0开始向前移动，移动到仍能包含string1的最大距离
【在 b******g 的大作中提到】
: input:
: string 1: “A B C”
: string 2: “BKKAFFCFBJCAHHBC”
: output:
: BJCA
: 目标：
: 要发现string2里面最短的substring，这个string包含所有的string1里面的字符。
: 有什么好的算法？
|
p*****2
发帖数: 21240 | |
b******g
发帖数: 1721 | 7 多谢recursive和bird1337的矫正。现在更清楚了。
另外，peking2，leetcode上的链接又没有？我正在看，还没找到。 |
r*******e
发帖数: 7583 | 8 http://leetcode.com/2010/11/finding-minimum-window-in-s-which.h
【在 b******g 的大作中提到】
: 多谢recursive和bird1337的矫正。现在更清楚了。
: 另外，peking2，leetcode上的链接又没有？我正在看，还没找到。
|
b******g
发帖数: 1721 | |
b*******3
发帖数: 109 | 10 贴个java solution O(n m) :
public String minWindow (String originalString, String patternString)
{
List valuePairs = new ArrayList();
int shortestWindowLength = originalString.length();
int shortestHolderIndex = 0;
for (int i=0; i< originalString.length(); i++)
{
if (patternString.indexOf(originalString.charAt(i))>=0)
{
ValuePair valuePair = new ValuePair(originalString.charAt(i)
, i);
valuePairs.add(valuePair);
if (valuePairs.size()>=patternString.length())
{
int matchStringLength = lastPatternMatched (valuePairs,
patternString);
if (matchStringLength > 0)
{
if (matchStringLength < shortestWindowLength)
{
shortestWindowLength = matchStringLength;
shortestHolderIndex = valuePairs.size() -1;
}
}
}
}
}
if (shortestHolderIndex ==0)
{
return null;
}
int beginIndex = valuePairs.get(shortestHolderIndex+1-patternString.
length()).pos;
int endIndex = valuePairs.get(shortestHolderIndex).pos;
return originalString.substring(beginIndex, endIndex+1);
}
private int lastPatternMatched (List valuePairs , String
patternString)
{
StringBuffer aBuffer = new StringBuffer();
for (int i= valuePairs.size()-1; i>= valuePairs.size()-
patternString.length(); i--)
{
ValuePair valuePair = valuePairs.get(i);
aBuffer.append(valuePair.letter);
}
if (isPermutation (aBuffer.toString(), patternString))
{
return valuePairs.get(valuePairs.size()-1).pos - valuePairs.get(
valuePairs.size()- patternString.length()).pos;
}
else
{
return -1;
}
}
public boolean isPermutation (String string0, String string1)
{
if (string0.length() != string1.length())
{
return false;
}
int[] charactersInNumber = new int[256];
for (int i=0; i< string0.length();i++)
{
int charFromString0 = string0.charAt(i);
charactersInNumber[charFromString0]++;
int charFromString1 = string1.charAt(i);
charactersInNumber[charFromString1]--;
}
for (int num : charactersInNumber)
{
if (num!= 0)
{
return false;
}
}
return true;
}
class ValuePair
{
char letter;
int pos;
public ValuePair(char letter, int pos)
{
this.letter = letter;
this.pos = pos;
}
public String toString()
{
return "(" + letter + "," + pos + ")";
}
}
unit test class:
@Test
public void testMinWindow()
{
String string1 = "ABC";
String string2 = "BKKAFFCFBJCAHHBC";
Assert.assertEquals(object.minWindow(string2, string1), "BJCA");
String string3 = "ADOBECODEBANC";
Assert.assertEquals(object.minWindow(string3, string1), "BANC");
String string4 = "ABA";
String string5 = "ADOBAEACODEBANC";
Assert.assertEquals(object.minWindow(string5, string4), "BAEA");
} |
