Kattis Phone List C#, Превышен лимит времени

Question

Я пытаюсь решить проблему со списком телефонов на Кэттис.

Это работает хорошо, но я не могу пройти второй контрольный пример! Останавливается с ошибкой "Превышен лимит времени". Я видел другие темы без рабочего решения...

using System;
using System.Collections.Generic;
using System.Linq;

namespace PhoneList
{
    class Program
    {
        static void Main(string[] args)
        {
            long testCases = Int64.Parse(Console.ReadLine());
            for (int i = 0; i < testCases; i++)
            {
                List<string> phoneNumbers = new List<string>();
                long phoneNumbersCount = Int64.Parse(Console.ReadLine());
                for (int j = 0; j < phoneNumbersCount; j++)
                {
                    phoneNumbers.Add(Console.ReadLine().Trim());
                }
                var consistent = phoneNumbers.FirstOrDefault(t2 => phoneNumbers.Exists(t1 => t1.StartsWith(t2) && !t1.Equals(t2)));
                switch (consistent)
                {
                    case null:
                        Console.WriteLine("YES");
                        break;
                    default:
                        Console.WriteLine("NO");
                        break;
                }
            }
        }
    }
}

Я переписывал это несколько раз, но сейчас я остановился. Я не могу понять, что работает так медленно, что превышает 3 секунды. Поскольку данные тестирования являются секретными, я понятия не имею, сколько цифр вводит Каттис...

Обновить

Заменен LINQ-запрос на:

            phoneNumbers.Sort();
            var consistent = true;
            for(int x = 1; x < phoneNumbers.Count; x++)
            {
                if (phoneNumbers[x].StartsWith(phoneNumbers[x - 1]))
                {
                    consistent = false;
                    break;
                }
            }

Answer 1

У меня есть два предложения:

1. Вместо сортировки по алфавиту с помощью phoneNumbers.Sort();, попробуйте отсортировать по длине: numbers.Sort((a, b) => a.Length - b.Length);. Интуиция заключается в том, что, поскольку строка с большей длиной не может быть префиксом более короткой строки, мы можем пропустить их проверку и сохранить некоторую работу (важно раннее спасение, как только мы обнаружим несоответствие).
2. Поскольку длина телефона составляет всего 10 цифр, можно перебрать его и сохранить каждый префикс в HashSet. HashSet дает нам время поиска O(1) для всех ранее вычисленных префиксов, поэтому временная сложность для каждого тестового примера составляет O(n) для проверок и O(n log(n)) для предварительной стоимости сортировки.

Вот код:

      using System;
using System.Collections.Generic;

namespace PhoneList
{
    class Program
    {
        static bool IsConsistent(List<string> numbers)
        {
            numbers.Sort((a, b) => a.Length - b.Length);
            var prefixes = new HashSet<string>();

            foreach (var n in numbers)
            {
                for (int i = 1; i < n.Length; i++)
                {
                    if (prefixes.Contains(n.Substring(0, i)))
                    {
                        return false;
                    }
                }

                prefixes.Add(n);
            }

            return true;
        }

        static void Main(string[] args)
        {
            int testCases = Int32.Parse(Console.ReadLine());

            for (int i = 0; i < testCases; i++)
            {
                int phoneNumbersCount = Int32.Parse(Console.ReadLine());
                var numbers = new List<string>();

                for (int j = 0; j < phoneNumbersCount; j++)
                {
                    numbers.Add(Console.ReadLine());
                }

                Console.WriteLine(IsConsistent(numbers) ? "YES" : "NO");
            }
        }
    }
}