C# - Finding which prefix applies

Question

Hi all, just looking for a bit of help in terms of the best way to proceed with the following problem:

I have a list of a bunch of dialled numbers, don't think you need me to show you but for e.g.

006789 1234
006656 1234
006676 1234
006999 1234
007000 1234
006999 6789

Now: I also have a list of prefixes (prefix being the bit dialled first, also tells you where the call is going(important bit)). Important also - they have leading 0's and, they are of differing length.

say for e.g.

006789 = australia
006789 = russia
006656 = france
006676 = austria
0069 = brazil
00700 = china

So what i am trying to do is write C# algorithm to find which prefix to apply.

The logic works as follows, say we have one dialled number and these prefixes

dialled number:0099876 5555 6565,
prefix1: 0099876 = Lyon (France)
prefix2: 0099 = France

Now both prefixes apply, except "the more detailed one" always wins. i.e. this call is to Lyon (France) and 0099876 should be result even though 0099 also applies.

Any help on getting me started with this algorithm would be great, because looking at it, im not sure if I should be comparing strings or ints! I have .Contains with strings, but as portrayed in my examples, that doesn't exactly work if the prefix is later in the number

i.e.

6999 6978
6978 1234

Cheers!!!

Answer 1

I guess you could sort your prefixes by length (longest first).

Then when you need to process a number, you can run through the prefixes in order, and stop when yourNumber.startsWith(prefix) is true.

Answer 2

If you already know what prefixes you're looking for, you're better off using a HashMap (I believe it's a Dictionary in C#) to store the prefix and the country it corresponds to. Then, for every number that comes in, you can do a standard search on all the prefixes in the list. Store the ones that match in a list, and then pick the longest match.

Answer 3

Another approach would be to shorten the dialed number by one from the right and test if this number is within the list:

Dictionary<string, string> numbers = new Dictionary<string, string>();

//Build up the possible numbers from somewhere
numbers.Add("006789", "australia");
numbers.Add("006790", "russia");
numbers.Add("006656", "france");
numbers.Add("006676", "austria");
numbers.Add("0069", "brazil");
numbers.Add("00700", "china");
numbers.Add("0099876", "Lyon (France)");
numbers.Add("0099", "France");

//Get the dialed number from somewhere
string dialedNumber = "0099 876 1234 56";

//Remove all whitespaces (maybe minus signs, plus sign against double zero, remove brackets, etc)
string normalizedNumber = dialedNumber.Replace(" ", "");

string searchForNumber = normalizedNumber;
while (searchForNumber.Length > 0)
{
    if(numbers.ContainsKey(searchForNumber))
    {
        Console.WriteLine("The number '{0}' is calling from {1}", dialedNumber, numbers[searchForNumber]);
        return;
    }
    searchForNumber = searchForNumber.Remove(searchForNumber.Length - 1);
}

Console.WriteLine("The number '{0}' doesn't contain any valid prefix", dialedNumber);

Answer 4

Looks like a good match for a trie to me. given your prefixes are guaranteed to be short this should be nice and quick to search. you could also find all matching prefixes at the same time. the longest prefix would be the last to match in the trie and would be O(m) to find (worst case) where m is the length of the prefix.

Answer 5

Find longest. Use LINQ:

prefixes.Where(p => number.StartsWith(p)).OrderByDescending(p => p.Length).FirstOrDefault();