Уникальная пара символов в двух строках

Question

Так что мне нужна помощь с упражнением, я застрял! Go Полегче, я довольно новичок в этом. Упражнение выполняется следующим образом:

Учитывая два массива одинаковой длины, определите, можно ли уникально заменить каждый символ из первого массива символом из второго, чтобы оба массива были равны. Отобразите пары символов между двумя массивами.

Пример 1: При следующем вводе: aab и ttd на консоли отобразится:

True
a => t
b => d

Пример 2 : С учетом следующего ввода: aba и ttd, консоль отобразит:

False

Во втором примере ответом будет False, поскольку для символа a нет уникального заменителя: и t и d соответствуют.

Я ломал голову над этим и, честно говоря, я чувствую, что больше не могу даже думать прямо. Изменяли код уже столько раз, что я уже почти не понимаю его. Это все еще проходит первый тест, хотя, кажется, продолжает проваливать тест с более длинным вводом строки. Например, при вводе: ala bala portocala и cuc dcuc efghijcuc консоль отображает True, а затем пары, что неверно. Ниже у вас есть мой POS-код, любые советы приветствуются.

static void Main(string[] args)
    {
        string a = Console.ReadLine();
        string b = Console.ReadLine();

        string one = string.Empty;
        string two = string.Empty;

        bool res = false;
        int count = 0;

        for (int i = 0; i < a.Length; i++) 
        {
            if (!one.Contains(a[i].ToString()))
            {
                if (!two.Contains(b[i].ToString())) 
                {
                    one += a[i];
                    two += b[i];
                }
            }
        }

        char[] firstPhrase = new char[one.Length];
        char[] scndPhrase = new char[two.Length];

        for(int i = 0; i < one.Length; i++) 
        {
            bool temp = false;
            for(int j = 0; j < two.Length; j++) 
            {
                if(firstPhrase[j] != one[i]) 
                {
                    for(int k = 0; k < scndPhrase.Length; k++) 
                    {
                        if(scndPhrase[j] == two[i]) { res = true; break; }

                    }
                    if(res == true) { break; }
                    else { continue; }
                }
                if(firstPhrase[j] == one[i]) 
                {
                    if (scndPhrase[j] == two[i]) { temp = true; continue; }
                    else { res = true; break; }
                }

            }
            if(temp == false) 
            {
                firstPhrase[count] = one[i];
                scndPhrase[count] = two[i];
                count++;
            }
            if(res == true) { break; }
        }


        if (res == true)
            Console.WriteLine(res);
        else
        {
            Console.WriteLine(!res);
            for (int i = 0; i < firstPhrase.Length; i++)
            {
                Console.WriteLine($"{firstPhrase[i]} => {scndPhrase[i]}");
            }
        }
        Console.Read();
    }

Я с нетерпением жду вашей критики, и я sh всех вас с наступающей Пасхой!

Редактировать : забыл упомянуть, так что извините, ребята. Тесты не позволяют использовать LINQ или любые другие директивы, LINQ был фактически первым, что я хотел попробовать.

Answer 1

Вот решение, использующее только пространство имен System.

Важная часть здесь - сначала поменять символы в обоих массивах на токены.

Это означает, что для "ala bala portocala" мы будет иметь:

{ 0, 1, 0, 2, 3, 0, 1, 0, 2, 4, 5, 6, 7, 5, 8, 0, 1, 0 }

Так что, когда будет найден новый символ (который раньше не появлялся), мы увеличиваем число на 1.

И вы можете видеть, что это хорошо работает для оценки если два массива символов совпадают с точки зрения этой интересной перспективы.

static int[] Tokenize(char[] array)
{
    int length = array.Length;
    int[] distinctArray = new int[length];
    int offset = 0;
    for (int i = 0; i < length; i++)
    {
        bool appearedBefore = false;
        for (int j = 0; j < i; j++)
        {
            if (array[j] == array[i])
            {
                appearedBefore = true;
                distinctArray[i] = distinctArray[j];
                break;
            }
        }
        if (!appearedBefore)
        {
            distinctArray[i] = offset;
            offset++;
        }
    }
    return distinctArray;
}

Тогда метод теста:

static void Test(char[] array1, char[] array2)
{
    Console.WriteLine("[{0}] VS [{1}]", new string(array1), new string(array2));

    int[] array1Tokenized = Tokenize(array1);
    int[] array2Tokenized = Tokenize(array2);

    for (int i = 0; i < array1.Length; i++)
    {
        if (array1Tokenized[i] != array2Tokenized[i])
        {
            Console.WriteLine("False");
            return;
        }
    }

    Console.Write("True");
    for (int i = 0; i < array1.Length; i++)
    {
        bool appearedBefore = false;
        for (int j = 0; j < i; j++)
        {
            if (array1[j] == array1[i])
            {
                appearedBefore = true;
                break;
            }
        }
        if (!appearedBefore && array1[i] != array2[i])
        {
            Console.Write(" {0} => {1}", array1[i], array2[i]);
        }
    }
    Console.WriteLine();
}

И результаты:

static void Main(string[] args)
{
    Test("ala bala portocala".ToCharArray(), "cuc dcuc efghijcuc".ToCharArray());

    Test("ala bala portocala".ToCharArray(), "cuc dcuc efghfjcuc".ToCharArray());

    Test("aab".ToCharArray(), "ttd".ToCharArray());
}

Вывод:

[ala bala portocala] VS [cuc dcuc efghijcuc]
False

[ala bala portocala] VS [cuc dcuc efghfjcuc]
True a => c l => u b => d p => e o => f r => g t => h c => j

[aab] VS [ttd]
True a => t b => d

Answer 2

Вот краткое решение, использующее только пространство имен System. По сути, все, что нам нужно сделать, это l oop через строки один раз параллельно, и для каждой позиции проверить, отображаются ли символы из каждой строки друг на друга. Существует три случая:

1. Символы ранее не отображались, в этом случае мы сопоставляем их друг с другом;
2. Символы уже сопоставлены друг с другом, и в этом случае мы продолжаем;
3. Любой символ уже сопоставлен, но не с другим символом, в этом случае нет правильного решения, поэтому мы возвращаем нуль.

Чтобы отслеживать В отображениях мы используем два параллельных массива, mappings и reverseMappings. Поскольку символы являются просто числами, мы можем использовать значение первого символа в качестве индекса в массиве отображения и установить значение, равное второму символу. То же самое для обратного отображения, но с противоположными символами. (Это будет работать до тех пор, пока массивы сопоставления достаточно велики, чтобы обрабатывать все возможные значения символов, которые мы ожидаем. Для ASCII максимальный размер равен 128. Для Юникода это должно быть 65536.) Поскольку мы go, мы сохраняем подсчет того, сколько пар мы уже видели. Это необходимо для того, чтобы мы знали, насколько велик размер возвращаемого массива (массив массивов n-на-2), который будет содержать фактические пары символов, необходимые для вывода. Мы строим это, сканируя массив отображений один раз, ища все отображения, которые имеют ненулевое значение.

public char[][] GetCharacterMappings(string s1, string s2)
{
    if (s1 == null || s2 == null || s1.Length != s2.Length) return null;

    // I'm assuming the inputs can only be in the ASCII character set;
    // If they can have any Unicode character, make this value larger (e.g. 65536) 
    const int maxCharValue = 128;
    char[] mappings = new char[maxCharValue];
    char[] reverseMappings = new char[maxCharValue];
    int pairCount = 0;

    for (int i = 0; i < s1.Length; i++)
    {
        char c1 = s1[i];
        char c2 = s2[i];

        if (mappings[c1] == 0 && reverseMappings[c2] == 0)
        {
            // these characters have not been mapped before
            mappings[c1] = c2;
            reverseMappings[c2] = c1;
            pairCount++;
        }
        else if (mappings[c1] != c2 || reverseMappings[c2] != c1)
        {
            // either character is already mapped to some other character
            return null;
        }
    }

    char[][] pairs = new char[pairCount][];
    int p = 0;
    for (int i = 0; i < maxCharValue; i++)
    {
        if (mappings[i] != 0)
            pairs[p++] = new char[] { (char)i, mappings[i] };
    }

    return pairs;
}

Процедура вывода просто проверяет, являются ли пары нулевыми, и, если нет, сбрасывает их все out:

public void WriteResult(char[][] pairs)
{
    Console.WriteLine(pairs != null);
    if (pairs != null)
    {
        for (int i = 0; i < pairs.Length; i++)
        {
            Console.WriteLine(pairs[i][0] + " => " + pairs[i][1]);
        }
    }
}

Вот рабочая демонстрация: https://dotnetfiddle.net/lBHKUY

Answer 3

Вот решение с LINQ:

var result = str1.Zip(str2, (f, s) =>  f.ToString() + s.ToString())
                 .GroupBy(c => c[0])
                 .Where(c => c.Select(d => d[1]).Distinct()
                 .Skip(1).Any()).Any() ? false : true;

Все, что вам нужно для запуска, это просто добавление using System.Linq к вашим директивам использования.

Вы можете увидеть результат онлайн здесь: https://dotnetfiddle.net/OF2cnO

Answer 4

Рассмотрите возможность использования словаря. NET. Когда функция ниже возвращает ноль, согласованное отображение отсутствует. Когда он возвращает словарь, его содержимое будет отображаться. Я скомпилировал это, я НЕ проверял это ..

public static Dictionary<char, char> BuildMapping(string s1, string s2)
{
    if (s1.Length != s2.Length) return null;
    Dictionary<char, char> result= new Dictionary<char, char>();
    for (int i = 0; i < s2.Length; i++)
    {
        if (result.ContainsKey(s1[i]))
            if (result[s1[i]] == s2[i]) continue;
            else return null;
        result[s1[i]] = s2[i];
    }
    return result;
}