yuhuiming
BAN USERclass Program
{
static void Main(string[] args)
{
string target = "ccdaabcdbb";
HashSet<string> patterns = new HashSet<string>();
patterns.Add("ab");
patterns.Add("cd");
Console.WriteLine(findMinLengthString(target, 0, patterns));
Console.ReadKey();
}
static string findMinLengthString(string target, int startIndex, HashSet<string> patterns)
{
if (string.IsNullOrEmpty(target))
{
return string.Empty;
}
if (patterns == null && patterns.Count == 0)
{
return target;
}
if (startIndex == target.Length - 1)
{
return patterns.Contains(target.ElementAt(startIndex).ToString()) ? string.Empty : target.ElementAt(startIndex).ToString();
}
string shortest = findMinLengthString(target, startIndex + 1, patterns);
string possibleShortest = target.ElementAt(startIndex) + shortest;
string currentMaxPattern = string.Empty;
foreach (string pattern in patterns)
{
if (possibleShortest.Contains(pattern) && pattern.Length > currentMaxPattern.Length)
{
currentMaxPattern = pattern;
}
}
if (!string.IsNullOrEmpty(currentMaxPattern))
{
possibleShortest = possibleShortest.Replace(currentMaxPattern, string.Empty);
}
string secondPossibleShort = target.Substring(startIndex);
if (!string.IsNullOrEmpty(currentMaxPattern))
{
secondPossibleShort = secondPossibleShort.Replace(currentMaxPattern, string.Empty);
}
if (secondPossibleShort.Length > possibleShortest.Length)
{
return possibleShortest;
}
return secondPossibleShort;
}
I think if we directly replace the occurrences, then we have to move the characters several times, so it is better to know which chars will be in final output and then append them.
- yuhuiming June 09, 2014