Running time of my C# algorithm
Posted by
dark_ai 30 Sep 2009 01:05
My C# Algorithm, error on Test 5 "Time limit exceeded". Help me make it faster. My email dark4ai@gmail.com
using System;
using System.Collections.Generic;
namespace timus1002
{
public class Word
{
public int wordscount = 0;
public int[] strs;
}
class Program
{
public static Dictionary<char, char[]> rules = new Dictionary<char, char[]>(10);
public static string[] strings = new string[16];
static bool TestWord(string word, string number)
{
if (number.Length < word.Length)
return false;
for (int i = 0; i < word.Length; i++)
if (Array.IndexOf<char>(rules[number[i]],word[i])==-1)
return false;
return true;
}
static Word TestNumber(string number, string[] dictionary, int min, int[] stros)
{
Word[] words = new Word[dictionary.Length];
int m = dictionary.Length + 1;
int mi = -1;
for (int i = 0; i < dictionary.Length;i++)
{
int[] resu = new int[stros.Length + 1];
for (int f = 0; f < resu.Length - 1; f++)
resu[f] = stros[f];
resu[resu.Length - 1] = i;
if (TestWord(dictionary[i], number))
{
if (dictionary[i].Length == number.Length)
{
Word result = new Word();
result.strs = resu;
result.wordscount = min + 1;
words[i] = result;
}
else
{
words[i] = TestNumber(number.Substring(dictionary[i].Length), dictionary, min + 1, resu);
}
if (words[i] != null && words[i].wordscount < m)
{
m = words[i].wordscount;
mi = i;
}
}
}
if (mi >= 0)
return words[mi];
return null;
}
static void Main(string[] args)
{
rules.Add('0', new char[]{ 'o', 'q', 'z' });
rules.Add('1', new char[]{ 'i', 'j' });
rules.Add('2', new char[]{ 'a', 'b', 'c' });
rules.Add('3', new char[]{ 'd', 'e', 'f' });
rules.Add('4', new char[]{ 'g', 'h'});
rules.Add('5', new char[]{ 'k', 'l'});
rules.Add('6', new char[]{ 'm', 'n'});
rules.Add('7', new char[]{ 'p', 'r', 's' });
rules.Add('8', new char[]{ 't', 'u', 'v' });
rules.Add('9', new char[]{ 'w', 'x', 'y' });
string end;
while (true)
{
end = Console.ReadLine();
if (end.Length != 2 && end != "-1")
{
int numbers = int.Parse(Console.ReadLine());
string[] dictionary = new string[numbers];
for (int i = 0; i < numbers; i++)
dictionary[i] = Console.ReadLine();
Word res = TestNumber(end, dictionary, 0, new int[0]);
if (res == null)
Console.WriteLine("No solution.");
else
{
string result = dictionary[res.strs[0]];
for(int k =1;k<res.strs.Length;k++)
result+=" "+dictionary[res.strs[k]];
Console.WriteLine(result);
}
}
else break;
}
Console.Read();
}
}
}