贴个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");
}
