Простое решение для проверки изоморфной строки, которая не может пройти 1 контрольный пример

Question

Ниже приведено мое решение проблемы изоморфных строк, приведенное в leetcode:

public bool IsIsomorphic(string s, string t)
    {
        int[] s1 = new int[s.Length];
        int[] t1 = new int[t.Length];
        bool isI = true;
        if (s1.Length > 0 && t1.Length > 0)
        {
            s1[0] = 0;
            int i = 1;
            int j = 1;
            for (i = 1; i < s.Length; i++)
            {
                if (s[i] == s[i - 1])
                {
                    s1[i] = 1;
                }
                else
                {
                    s1[i] = 0;
                }
            }
            for (j = 1; j < t.Length; j++)
            {
                if (t[j] == t[j - 1])
                {
                    t1[j] = 1;
                }
                else
                {
                    t1[j] = 0;
                }
            }
            for (int k = 0; k < s1.Length; k++)
            {
                if(s1[k] != t1[k])
                {
                    isI = false;
                }
            }
        }
        else
        {
            isI = true;
        }
        return isI;
    }

которые прошли 29/30 контрольных примеров, но не прошли следующий контрольный пример, который смехотворно длинный. Поделиться кодом с вводом в Google Drive:

https://docs.google.com/document/d/1UkG8Rc6VItiihwvqzJdM3uMHIX-BCsslJ_lVklkxvq8/edit?usp=sharing

Любая помощь будет отличной.

Answer 1

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

Предположение, что вы, вероятно, сделали, что привело вас к ошибкам.

Вы код алгоритма + догадка о том, что вы пытались.

Вы перебираете каждую строку и проверяете, есть ли дубликаты в том же индексе, но на противоположных сторонах, если они помечены, как 1, иначе 0. То же самое относится и к другой строке. Когда вы заканчиваете итерацию обеих строк, вы проверяете, что эти значения равны.

Это ложное предположение.

Ложное предположение № 1: наложение только на 2 символа
Только наложение двух чисел 0, 1 для представления повторения в строке невозможно и, следовательно, неверно.
Что происходит, когда у нас есть пара повторяющихся персонажей? скажем, банан по текущему алгоритму, вы не можете представить оба B, a и n только с 2 символами.
Понимание: теперь мы понимаем, что для каждого уникального персонажа нам нужен новый номер.

Ложное предположение № 2: Маркировка повторяющихся символов
Давайте работать в предположении, что для каждого нового символа мы выделяем цифру.

1. Как мы можем определить новых персонажей? Это означает, что нам нужно сканировать старый символ, чтобы увидеть, существует ли он уже, что означает, что мы не можем выполнить ОДНУ быструю очистку нашей строки, это означает, что нам нужно сканировать каждый текущий I(индексный) символ на 0-(I). -1) чтобы увидеть, если это слово уже существовало. Что приводит нас к другой проблеме: у нас есть цифры, а не реальные символы? Что мы сейчас делаем? Создать еще один массив для хранения каждого уникального числа символа? это означает, что другой массив (сложность и память).

2. Допустим, у нас есть 6 длинных строк, вы только думаете, что можете сканировать повторяющиеся символы, сравнивая значения по их индексам 0,5 | 1,4 | 2, 3 этого недостаточно, чтобы установить, что они повторяются, потому что вы работаете в предположении, что знаете, какой порядок (индекс) предполагают повторяющиеся символы в одной строке, что мы не можем предвидеть. например: banana => b!= a, a!= n, n!= a Это означает, что в этом слове нет повторяющихся символов? Это явно неправильно.

Как вы видите, мы можем чувствовать запах чего-то смешного, много хлопот за такую ​​маленькую часть.

Все дело в дизайне, если бы мы потратили больше времени на то, как более эффективно атаковать эту проблему, и на инструменты, которые у нас есть в нашем распоряжении (мы можем сами создавать инструменты [Array over Dictionary]) выяснил все эти проблемы.

Всегда инвестируйте в дизайн, это стоит инвестировать, и вы не пожалеете.

Решение № 1:
Зачем использовать цифры? давайте использовать реальные символы. В этом случае другой вариант решения - лучший выбор.

public bool IsIsomorphic(string s, string t)
{
    if (s.Length != t.Length)
    {
        return false;
    }

    bool result = true;
    var relation = new Dictionary<char, char>();
    for (int i = 0; i < s.Length; i++)
    {
        char sChar = s[i];
        char tChar = t[i];
        char c;
        if (relation.TryGetValue(sChar, out c))
        {
            if (c != tChar)
            {
                result = false;
                break;
            }
        }
        else if (relation.ContainsValue(tChar))
        {
            result = false;
            break;
        }
        else
        {
            relation.Add(sChar, tChar);
        }
    }
    return result;
}

Решение № 2:
Больше памяти, меньше читаемости и без использования внешних инструментов (проверка в конце - простое сравнение значений массива)

public bool IsIsomorphic3(string s, string t)
{
    if (s.Length != t.Length)
    {
        return false;
    }

    int[] firstNumbering = new int[26];
    int[] firstStringOrder = new int[s.Length];
    int firstCounter = 0;
    for (int i = 0; i < s.Length; i++)
    {
        char c = s[i];
        if (firstNumbering[c - 'a'] == 0)
        {
            firstNumbering[c - 'a'] = ++firstCounter;
        }
        firstStringOrder[i] = firstNumbering[c - 'a'];
    }

    int[] secondNumbering = new int[26];
    int[] secondStringOrder = new int[t.Length];
    int secondCounter = 0;
    for (int j = 0; j < t.Length; j++)
    {
        char c = t[j];
        if (secondNumbering[c - 'a'] == 0)
        {
            secondNumbering[c - 'a'] = ++secondCounter;
        }
        secondStringOrder[j] = secondNumbering[c - 'a'];
    }

    return firstStringOrder.SequenceEqual(secondStringOrder); // Comparing values using Linq
}