9am

Archive for the ‘Strings’ Category

What’s The Number Again ?

In Algorithms, Graphs, Programming, Strings on September 16, 2010 at 9:49 pm
The previous post “What’s The Number” had a non-recursive implementation. Here is a recursive way of doing the same. It’s not as bad to have a recursive implementation as the max recursion depth is limited by the length of  a telephone number. If the input was longer / without an upper bound, recursion would be a bad move. This Recursive algorithm does a Depth First walk. A recursive Breadth First walk is much more painful to implement and has a higher memory overhead.
/*
Given a telephone number like 4156434531, get all possible names that would match it.
e.g. If the number is 23, the names could be “ad”, “bd”, “cd”, “ae” etc..
*/
public static class TelNumber
{
private static char[][] KeyChars = new char[10][];
static TelNumber()
{
KeyChars[0] = new char[]{‘+’};
KeyChars[1] = new char[]{‘ ‘};
KeyChars[2] = new char[]{‘a’,’b’,’c’};
KeyChars[3] = new char[]{‘d’,’e’,’f’};
KeyChars[4] = new char[]{‘g’,’h’,’i’};
..
}
public static void PrintCombination(StringBuffer prefix, int[] tel_no)
{
int index = prefix.Count;
if (index >= tel_no.Length)
{
System.Console.Writeline(prefix);
return;
}
foreach(char c in KeyChars[tel_no[index]])
{
prefix.Add(c);
PrintCombination(prefix, tel_no);
prefix.RemoveLastChar();
}
}
Advertisements

Fuzzy RegexMatcher

In Programming, Strings on September 4, 2010 at 2:41 pm

/*
This Fuzzy RegexMatcher does not handle *,?, ^ etc., but, it takes in a tolerance/forgiveness factor.
With a forgiveness value of 1, regex “ac” would match strings like “abc” or “ad” or “c”.  With a forgiveness factor of 0, the match would fail.
*/

using System;
namespace StringHelpers
{
public static partial class RegexMatcher
{
public static bool AreSimilar(char[] str, char[] pattern, int forgiveness)
{
// Args check todo
for (int i = 0; i <= str.Length – pattern.Length; i++)
{
if (AreSimilar(str, pattern, i/*str index*/, 0/*pattern index*/, forgiveness)) return true;
}
return false;
}
private static bool AreSimilar(char[] str, char[] pattern, int si, int pi, int forgiveness)
{
if (pi >= pattern.Length) return true;
if (si >= str.Length) return false;
if (str[si] == pattern[pi])
{
return AreSimilar(str, pattern, si + 1, pi + 1, forgiveness);
}
else if (forgiveness > 0)
{
return AreSimilar(str, pattern, si, pi + 1, forgiveness – 1)|| AreSimilar(str, pattern, si + 1, pi + 1, forgiveness – 1);
}
return false;
}
}
}