Подтвердить что ты не робот

Как обобщать мой алгоритм, чтобы определить, является ли одна строка вращением другого

Таким образом, я сталкивался с различными проблемами для просмотра предстоящих собеседований, и один из них, с которым я столкнулся, определяет, являются ли две строки вращением друг друга. Очевидно, что я едва ли первый человек, решивший эту проблему. Фактически, я обнаружил, что моя идея для решения этого похоже на подход, использованный в этом вопросе.

Полное раскрытие: у меня есть связанный вопрос в Math SE, который фокусируется на свойствах с более математической точки зрения (хотя стоит отметить, что способ, которым я пытался формулировать идеи, стоящие за этим, в конечном итоге являются неправильными по причинам, которые объясняются там).

Здесь идея (и это похоже на подход, использованный в связанном вопросе): предположим, что у вас есть строка abcd и вращение cdab. Очевидно, что оба cd и ab являются подстроками cdab, но если вы объедините их вместе, вы получите abcd.

В принципе, поворот просто влечет за собой перемещение подстроки от конца строки до начала (например, мы построили cdab из abcd, перемещая cd от конца строки до начала строки).

Я придумал подход, который работает в очень ограниченном случае (если обе подстроки состоят из последовательных букв, как в примере), но в противном случае он не работает (и я приведу пример прохождения и сбоя случаев и вводов/выходов ниже кода). Я пытаюсь выяснить, возможно ли (или даже стоит) попытаться исправить его для работы в общем случае.

    public bool AreRotations(string a, string b)
    {
        if (a == null)
            throw new ArgumentNullException("a");
        else if (b == null)
            throw new ArgumentNullException("b");
        else if (a.Trim().Length == 0)
            throw new ArgumentException("a is empty or consists only of whitespace");
        else if (b.Trim().Length == 0)
            throw new ArgumentException("b is empty or consists only of whitespace");

        // Obviously, if the strings are of different lengths, they can't possibly be rotations of each other
        if (a.Length != b.Length)
            return false;

        int[] rotationLengths = new int[a.Length];

        /* For rotations of length -2, -2, -2, 2, 2, 2, the distinct rotation lengths are -2, 2
         * 
         * In the example I give below of a non-working input, this contains -16, -23, 16, 23
         * 
         * On the face of it, that would seem like a useful pattern, but it seems like this
         * could quickly get out of hand as I discover more edge cases
         */
        List<int> distinctRotationLengths = new List<int>();
        for (int i = 0; i < a.Length; i++)
        {
            rotationLengths[i] = a[i] - b[i];

            if (i == 0)
                distinctRotationLengths.Add(rotationLengths[0]);
            else if (rotationLengths[i] != rotationLengths[i - 1])
            {
                distinctRotationLengths.Add(rotationLengths[i]);
            }
        }

        return distinctRotationLengths.Count == 2;
    }

И теперь для выборки входов/выходов:

        StringIsRotation rot = new StringIsRotation();

        // This is the case that doesn't work right - it gives "false" instead of "true"
        bool success = rot.AreRotations("acqz", "qzac");

        // True
        success = rot.AreRotations("abcdef", "cdefab");

        // True
        success = rot.AreRotations("ablm", "lmab");

        // False, but should be true - this is another illustration of the bug
        success = rot.AreRotations("baby", "byba");

        // True
        success = rot.AreRotations("abcdef", "defabc");

        //True
        success = rot.AreRotations("abcd", "cdab");

        // True
        success = rot.AreRotations("abc", "cab");

        // False
        success = rot.AreRotations("abcd", "acbd");

        // This is an odd situation - right now it returns "false" but you could
        // argue about whether that correct
        success = rot.AreRotations("abcd", "abcd");

Возможно ли/целесообразно спасти этот подход и все равно быть O (n), или я должен просто пойти с одним из подходов, описанных в сообщении, которое я связал? (Обратите внимание, что это не производственный код или домашнее задание, это чисто для моего собственного обучения).

Изменить: Для дальнейшего пояснения, основанного на комментариях, здесь есть два вопроса: во-первых, этот алгоритм можно устранить? Во-вторых, стоит ли его исправлять (или я просто попробую другой подход, как описано в ответах или другом вопросе, к которому я привязался)? Я думал о нескольких возможных исправлениях, но все они касались либо неэлегантного аргумента в отношении конкретного случая, либо создания этого алгоритма O (n ^ 2), оба из которых в первую очередь убьют точку алгоритма.

4b9b3361

ОТВЕТЫ

Ответ 1

Предположим, что первая строка - S, а вторая - S ', очевидно, если они имеют разную длину, тогда мы выводим их не вращение друг друга. Создайте строку S '' = SS. На самом деле конкатенация S на себя. Тогда, если S, S '- вращение друг друга, мы найдем подстроку S' в S '' по KMP Алгоритм в O(n), иначе мы выводим, что они не являются вращением друг друга. BTW, если вы ищете быстрый практический алгоритм, а вместо KMP используйте алгоритм Бойера Мура.

Чтобы более подробно ответить на вопрос, я бы сказал, что я не ожидаю простого алгоритма для этого специального случая проблемы с сопоставлением строк. Поэтому, имея в виду этот фон, я не думаю, что легкая модификация вашего алгоритма может работать. На самом деле поле алгоритмов согласования строк очень хорошо развито. Если для этого частного случая существует несколько более простой алгоритм, чем sth, такой как алгоритмы KMP или суффикс-дерева, то все же я думаю, что изучение этих общих алгоритмов может помочь.

Ответ 2

Будет что-то вроде этой работы?:

private bool IsRotation(string a, string b)
{
    if (a.Length != b.Length) { return false; }
    for (int i = 0; i < b.Length; ++i)
    {
        if (GetCharactersLooped(b, i).SequenceEqual(a))
        {
            return true;
        }
    }
    return false;
}

private IEnumerable<char> GetCharactersLooped(string data, int startPos)
{
    for (int i = startPos; i < data.Length; ++i)
    {
        yield return data[i];
    }
    for (int i = 0; i < startPos; ++i)
    {
        yield return data[i];
    }
}

P.S. Это вернет true для abcd = abcd, так как вы можете считать его полным вращением. Если это не требуется, измените начало цикла с 0 на 1 в первой функции.

Ответ 3

Если вы ищете только метод, который проверяет, является ли строка поворот другой строки, это реализация С# функции, с которой вы связывались (насколько я знаю, это самый быстрый способ решить эту проблему особая проблема):

bool IsRotation(string a, string b)
{
    if (a == null || b == null || a.Length != b.Length)
        return false;

    return (a + a).Contains(b);
}

Если вы запрашиваете обратную связь по своему алгоритму, я не уверен, что понимаю, что ваш алгоритм пытается сделать. Похоже, вы пытаетесь обнаружить поворот, сохраняя разницу значений char в строке и видя, суммируются ли они на 0? Или, если список уникальных различий содержит пары зеркал (пары (x,y) где x = -y)? Или просто, если число уникальных различий четное? Или что-то еще, что мне не хватает в вашем описании?

Я не уверен, что то, что вы делаете, может быть обобщено, просто потому, что оно так сильно зависит от символов в словах, что он может не адекватно проверить порядок, в котором они представлены. И даже если бы вы могли, это было бы только научное упражнение, поскольку вышеупомянутый метод будет намного быстрее и эффективнее, чем ваш метод может когда-либо быть.