saisatish
BAN USERpublic static bool ContainsEx(string s1, string s2)
{
//s1 contains s2
return String.Concat(s1.OrderBy(c => c).Distinct()).Contains(String.Concat(s2.OrderBy(c => c)));
}
public static string MinConsecutiveSubstring(string s, string t)
{
Queue<int> matches = new Queue<int>();
string matched = "";
int bestStartWindow = -1;
int startWindow = -1;
int length = 0;
int minLength = Int32.MaxValue;
for(int i =0; i < s.Length; i++)
{
if (t.Contains(s[i]))
{
matched = matched + s[i];
matches.Enqueue(i);
}
while (ContainsEx(matched,t))
{
// end window reached
startWindow = matches.Dequeue();
length = i - startWindow+1;
if (length < minLength)
{
minLength = length;
bestStartWindow = startWindow;
// store start and end later on
}
// remove first character from matched and check if still matched
matched = matched.Substring(1);
}
}
if (bestStartWindow > -1)
return s.Substring(bestStartWindow, minLength);
else
return string.Empty;
}
public SortedDictionary<int, List<Node<T>>> dict = new SortedDictionary<int, List<Node<T>>>();
public void VerticalTraverse(Node<T> node, int pos )
{
Queue<Tuple<int, Node<T>>> q = new Queue<Tuple<int, Node<T>>>();
q.Enqueue(new Tuple<int, Node<T>>(0,node));
while (q.Count > 0)
{
var n = q.Dequeue();
if (!dict.ContainsKey(n.Item1))
{
dict.Add(n.Item1, new List<Node<T>>());
}
dict[n.Item1].Add(n.Item2);
if (n.Item2.Left != null) q.Enqueue(new Tuple<int, Node<T>>(n.Item1-1,n.Item2.Left));
if (n.Item2.Right != null) q.Enqueue(new Tuple<int, Node<T>>(n.Item1 + 1, n.Item2.Right));
}
}
// Call it like this
btree.VerticalTraverse(btree.Root, 0);
Debug.WriteLine("Vertical Traverse" + String.Join("->", btree.dict.Values.ToArray().SelectMany(p=>p).Select(p=>p.Data)));
- saisatish May 22, 2016