HackerRank: Count string (III)

April 9, 2016

 Problem statement

 Solution to study:

Julia's C# practice with bugs


 The code has time out issue, wrong answer, and it only scores 3 out of 80.

code source:

https://www.hackerrank.com/casaro

Statistics:

Time spent:  1:00pm - 3:00pm
Go through test cases

C# code to study, also show C# source code here.

	using System;
	using System.Collections.Generic;
	using System.IO;
	class CountStrings
	{
	static Dictionary<string, long> knowen = new Dictionary<string, long>();
	static void Main(string[] args)
	{
	long countTestCases = Convert.ToInt64(System.Console.ReadLine());
	for (long k = 0; k < countTestCases; k++)
	{
	string[] input = System.Console.ReadLine().Split(' ');
	string regexp = input[0];
	int n = Convert.ToInt32(input[1]);
	long result = Count(regexp, n);
	Console.WriteLine(result);
	}
	}
	/*
	* Julia's comment:
	Test case A:
	1
	ab 2
	Program crashes, the form should be (ab) instead, check the definition.
	Test case B:
	1
	(a|b) 1
	Test case C:
	1
	(ab) 2
	Test case D:
	1
	((ab)) 2
	or operation:
	for (int i = 0; i <= n; i++)
	{
	result += Count(r1, i) * Count(r2, n - i);
	result %= 1000000007;
	}
	go through all the cases:
	i = 0, 1, 2, 3
	four iterations
	Test case D:
	((ab)|(ba)) 2
	Test case E:
	(ab*) 3
	*/
	static long Count(string regexp, int n)
	{
	if (regexp.Length == 1)
	{
	if (n == 1)
	return 1;
	else
	return 0;
	}
	if (knowen.ContainsKey(regexp + n))
	{
	return knowen[regexp + n];
	}
	regexp = regexp.Substring(1, regexp.Length - 2);
	long result;
	if (regexp[regexp.Length - 1] == '*')
	{
	string r1 = regexp.Substring(0, regexp.Length - 1);
	if (n == 0)
	return 1;
	result = 0;
	for (int i = 1; i <= n; i++)
	{
	result += Count(r1, i) * Count("(" + regexp + ")", n - i);
	result %= 1000000007;
	}
	}
	else if (isOrExpression(regexp) >= 0)
	{
	int posDevider = isOrExpression(regexp);
	string r1 = regexp.Substring(0, posDevider);
	string r2 = regexp.Substring(posDevider + 1, regexp.Length - posDevider - 1);
	result = Count(r1, n) + Count(r2, n);
	result %= 1000000007;
	}
	else
	{
	int posDevider = isAndExpression(regexp);
	string r1 = regexp.Substring(0, posDevider + 1);
	string r2 = regexp.Substring(posDevider + 1, regexp.Length - posDevider - 1);
	result = 0;
	for (int i = 0; i <= n; i++)
	{
	result += Count(r1, i) * Count(r2, n - i);
	result %= 1000000007;
	}
	}
	knowen.Add("(" + regexp + ")" + n, result);
	return result;
	}
	/*
	* Test case:
	* (a|b) 1
	* return yes
	*
	*/
	private static int isOrExpression(string regexp)
	{
	Stack<char> braces = new Stack<char>();
	for (int i = 0; i < regexp.Length; i++)
	{
	char c = regexp[i];
	if (c == '(')
	{
	braces.Push(c);
	}
	else if (c == ')')
	{
	braces.Pop();
	}
	else if (c == '|')
	{
	if (braces.Count == 0)
	return i;
	}
	}
	return -1;
	}
	/*
	Test case:
	(ab) 2
	regexp ab
	Test case:
	((ab)) 2
	* */
	private static int isAndExpression(string regexp)
	{
	Stack<char> braces = new Stack<char>();
	if (regexp[0] == 'a' || regexp[0] == 'b')
	return 0;
	for (int i = 0; i < regexp.Length; i++)
	{
	char c = regexp[i];
	if (c == '(')
	{
	braces.Push(c);
	}
	else if (c == ')')
	{
	braces.Pop();
	if (braces.Count == 0)
	return i;
	}
	}
	return -1;
	}
	}

view raw Hackerrank_countString_studyCode.cs hosted with ❤ by GitHub

April 10, 2016

Action items:

Need to think about in computer theory, NFA, DFA, and argue that the above solution in theory has flaws.

Follow up after 12 months

Julia checked the blog statistics, and the blog has a lot of views recently. So, she reformatted the blog style and she will review the algorithm very soon, and also post a question on code review.