C# алгоритм перебора паролей

216

26 ноября 2017, 11:43

Всем привет! По учебе нужно написать код (обязательно рекурсивный!), который бы по заданному слову перебирал все возможные пароли, полученные из этого слова заменой регистра. Как пример из данного слова "код" он выводил бы "коД", "кОд", "кОД", "Код", "КоД", "КОд", "КОД". По условию на вход подаются слова только в нижнем регистре. Код, который я написал, справляется с задачей, но при определенном вводе получает ошибку

Time limit exceeded

Как можно модернизировать код, чтобы такой ошибки не было, надеюсь на сообщество. Спасибо)

public class CaseAlternatorTask
{
    public static List<string> AlternateCharCases(string lowercaseWord)
    {
        var result = new List<string>();
        AlternateCharCases(lowercaseWord.ToCharArray(), 0, result);
        return result;
    }
        static void AlternateCharCases(char[] word, int startIndex, List<string> result)
        {
            bool[] helper = new bool[word.Length];
            Solver(word, startIndex, result);
        }
        static void Solver(char[] word, int startIndex, List<string> result)
        {
            var subWord = word.ToArray();
            if (startIndex == word.Length)
            {
                result.Add(new string(word));
                DelTheSame(result);
                return;
            }
            word[startIndex] = char.ToLower(word[startIndex]);
            Solver(word, startIndex + 1, result);
            word[startIndex] = char.ToUpper(word[startIndex]);
            Solver(word, startIndex + 1, result);
        }
        static List<string> DelTheSame (List<string> result)
        {
            for (int i = 0; i < result.ToArray().Length; i++)
            {
                for (int j = i + 1; j < result.ToArray().Length; j++)
                {
                    if (result[i] == result[j])
                    {
                        result.RemoveAt(j);
                    }
                    else continue;
                }
            }
            return result;
        }
}

Answer 1

Обратите внимание на свой код. Допустим, у нас есть строка длиной N. В таком случае, у нас есть 2^N вариантов паролей. Для каждого из вариантов паролей вы вызываете функцию DelTheSame, которая содержит 2 вложенных цикла, что работает за (2^N)^2. Таким образом, ваш алгоритм выполняет как минимум за (2^N)^3 операций (то есть 2 в степени N и это все в степени 3). Как ускорить алгоритм? Я предлагаю избавиться от вызова метода DelTheSame. Для чего он нужен? Чтобы избавиться от дубликатов в результате. Почему мы получаем дубликаты в результате? Потому что некорые символы выглядят одинаково в разных регистрах (например, пробел). А что, если сравнивать символ в нижнем регистре и и верхнем, и если они одинаковые, то перебирать только по 1 варианту? Например:

static void Solver(char[] word, int startIndex, List<string> result)
{
    var subWord = word.ToArray();
    if (startIndex == word.Length)
    {
        result.Add(new string(word));
        return;
    }
    var lower = char.ToLower(word[startIndex]);
    var upper = char.ToUpper(word[startIndex]);
    word[startIndex] = lower;
    Solver(word, startIndex + 1, result);
    if (lower != upper)
    {
        word[startIndex] = upper;
        Solver(word, startIndex + 1, result);
    }
}

После этих изменений в результирующем списке не будет дубликатов, и функция DelTheSame больше не нужна. Теперь время работы алгоритма 2^N, что гораздо быстрее того, что было.