c.prashanth85
BAN USERSimple recursion
class Program
{
static void Main( string[] args )
{
string s = Console.ReadLine();
string o = null;
recurse( s, o, 0 );
}
private static void recurse( string s, string o, int start )
{
for ( int i = start; i < s.Length; i++ )
{
o = o + s[i];
Console.WriteLine( o );
recurse( s, o, i + 1 );
o = o.Remove( o.Length - 1 );
}
}
}
Logic around handling ')', if input is '(' it is just added to stack and stack count is added at the end to account for it.
private static void makevalidparent(string s)
{
Stack<char> parent = new Stack<char>();
int makevalid = 0;
foreach(char c in s)
{
if ( c == '(' )
parent.Push( c );
else if (c == ')')
{
if(parent.Count == 0)
{
makevalid++;
}
else
{
parent.Pop();
}
}
}
makevalid = makevalid + parent.Count;
Console.WriteLine( makevalid );
}
Building up a graph dynamically and returning when target word is found
{
Queue<Tuple<string,int>> grph = new Queue<Tuple<string,int>>();
HashSet<string> words = new HashSet<string>() {"cat","bat","bet","bot","bog","dog","cot","dot","dog"};
HashSet<string> visited = new HashSet<string>();
string allEnglishCharacters = "abcdefghijklmnopqrstuvwxyz";
string start = Console.ReadLine();
string end = Console.ReadLine();
grph.Enqueue( new Tuple<string,int>( start, 1 ));
int level = -1;
while(grph.Count > 0)
{
var target = grph.Dequeue();
string src = target.Item1;
for ( int i = 0; i < src.Length; i++ )
{
foreach(char c in allEnglishCharacters)
{
string res = src.Substring( 0, i ) + c + src.Substring( i+1 );
//Optimization to reduce unnecessary checks
if ( visited.Contains( res ) )
{
continue;
}
else
{
visited.Add( res );
}
// if target word found exit
if ( res == end )
{
level = target.Item2 + 1;
break;
}
// if found in dictionary add
if(words.Contains(res))
{
grph.Enqueue(new Tuple<string,int> (res, target.Item2 + 1 ));
}
}
if ( level != -1 )
break;
}
if ( level != -1 )
break;
}
Console.WriteLine( level );
}
O(n+m) approach which uses sorted property of lists to determine union and intersection.
using System;
using System.Collections.Generic;
namespace ConsoleApplication24
{
class Program
{
static void Main( string[] args )
{
List<int> l1 = new List<int>() { 1, 23, 26, 40, 45 };
List<int> l2 = new List<int>() { -1, 2, 6, 26, 40, 50, 75 };
foreach ( int val in union( l1, l2 ) )
Console.Write( val + " " );
Console.WriteLine();
foreach ( int val in intersect( l1, l2 ) )
Console.Write( val + " " );
}
private static List<int> union( List<int> l1, List<int> l2 )
{
if ( l1.Count == 0 )
return l2;
if ( l2.Count == 0 )
return l1;
List<int> op = new List<int>();
int start1 = 0;
int start2 = 0;
int end1 = l1.Count;
int end2 = l2.Count;
while ( start1 < end1 && start2 < end2 )
{
if ( l1[start1] <= l2[start2] )
{
op.Add( l1[start1] );
start1++;
}
else
{
op.Add( l2[start2] );
start2++;
}
}
if ( start1 == end1 )
{
while ( start2 < end2 )
{
op.Add( l2[start2] );
start2++;
}
}
if ( start2 == end2 )
{
while ( start1 < end1 )
{
op.Add( l1[start1] );
start1++;
}
}
return op;
}
public static List<int> intersect( List<int> l1, List<int> l2 )
{
if ( l1.Count == 0 )
return l2;
if ( l2.Count == 0 )
return l1;
List<int> op = new List<int>();
int start1 = 0;
int start2 = 0;
int end1 = l1.Count;
int end2 = l2.Count;
while ( start1 < end1 && start2 < end2 )
{
if ( l1[start1] == l2[start2] )
{
op.Add( l1[start1] );
start1++;
start2++;
}
else if ( l1[start1] < l2[start2] )
{
start1++;
continue;
}
else
{
start2++;
}
}
return op;
}
}
}
O(NLogN) solution, based on sorting by Start value and then using stack to handle overlaps
- c.prashanth85 October 20, 2015