Превратить первую строку во вторую, заменяя одни буквы на другие

Question

Задание:

На вход подается 2 строки. Нужно определить, можно ли превратить первую строку во вторую, заменяя одни буквы на другие, с учетом следующих правил:

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

Пример 1
Входные данные: привет прикол
Выходные данные: 1
Преобразования (выводить не нужно):
в ⇒ к (прикет)
е ⇒ о (прикот)
т ⇒ л (прикол)

Пример 2
Входные данные: ааббдд ддббаа
Выходные данные: 1
Преобразования (выводить не нужно):
д ⇒ я (ааббяя)
а ⇒ д (ддббяя)
я ⇒ а (ддббаа)

Пример 3
Входные данные: абаб ааах
Выходные данные: 0
Преобразовать нельзя, так как 'б' не сможет оказаться одновременно 'а' и 'х'.

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

function solve(line) {
  function changeLetterInWord(word, fromLetter, whichLetter) {
    word = word.split('');
    for (let i = 0; i < word.length; i++) {
      if (word[i] === fromLetter) {
        word[i] = whichLetter;
      }
    }
    return word.join('');
  }
  line = String(line);
  const strArr = line.split(' ');
  const russianRegExp = /^[а-яё]+$/i;
  if (strArr.length !== 2 ||
    strArr[0].length !== strArr[1].length ||
    !russianRegExp.test(strArr[0]) ||
    !russianRegExp.test(strArr[1])
  ) {
    return false;
  }

  // const russianAlphabet = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя';
  for (let i = 0; i < strArr[0].length; i++) {
    const item = strArr[0][i];
    if (strArr[0][i] !== strArr[1][i]) {
      strArr[0] = changeLetterInWord(strArr[0], strArr[0][i], strArr[1][i]);
    }
  }
  return strArr.join(' ');
}

const str = 'привет прикол';
console.log(str);
console.log(solve(str));

Answer 1

Описание решения.

Есть два слова: first и second. Задача собственно ясна. Создадим специальную функцию check, принимающую две строки и возвращающую true, если они соответствуют условиям задачи, иначе false.

Путь решения:

Если длины слов не равны, то возвращаем ноль
Цикл i от 0 до длины первого слова (можно и второго, т.к. они равны):
Записывам i-ю букву первого слова в переменную first_letter, а i-ю букву второго слова - в переменную second_letter.
Проверяем в цикле j от i до длины первого слова (ищем, есть ли еще first_letter в first ИЛИ second_letter в second
Если first_letter равно j-й букве слова first (то есть нашли повторяющуюся букву, теперь у нас буквы i и j в первом слове совпадают), НО second_letter НЕ равно j-й букве второго слова (то есть во втором слове буквы i и j не совпадают), то возвращаем false. То же самое, если second_letter равно j-й букву второго слова, НО first_letter НЕ равно j-й букве первого слова (наоборот).
Циклы проходят так по всем буквам обоих слов. Если никаких ошибок найдено не было, то по завершению обоих циклов возвращаем true.
Саму функцию check() вызываем откуда надо. Я вызвал из main().

#include <iostream>
using namespace std;

bool check(string first, string second) {
    if (first.length() != second.length()) return false;

    for (int i = 0; i < first.length(); i++) {
        char first_letter = first[i];
        char second_letter = second[i];
        for (int j = i; j < first.length(); j++) {
            if ((first_letter == first[j] && second_letter != second[j]) || 
                (first_letter != first[j] && second_letter == second[j])) 
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    string first, second;
    cin >> first >> second;

    check(first, second);
}

Помучился я с вашим вопросом, потому что затупил, как правильнее реализовать. Но вроде все работает хорошо: я проверил, - так что будет для вас ответ, а для меня опыт:)

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

ВАЖНО! МОЙ КОД ПРОВЕРЯЕТ СТРОКИ В ОБЕ СТРОКИ, Т.Е. НАПРИМЕР ИЗ HELLO НЕЛЬЗЯ ПОЛУЧИТЬ ASDFG, Т.К. L НЕ МОЖЕТ ОДНОВЕМЕННО БЫТЬ И D, И F - МОЙ КОД ВЫДАСТ FALSE (КАК И НАДО), ОДНАКО ОН ВЫДАСТ ТОЖЕ САМОЕ И В ОБРАТНУЮ СТОРОНУ. ЧТОБЫ ЭТО УБРАТЬВОТ ЗДЕСЬ:

            if ((first_letter == first[j] && second_letter != second[j]) || 
                (first_letter != first[j] && second_letter == second[j]))

УБЕРИТЕ ВТОРУЮ СТРОКУ И УБЕРИТЕ || НА КОНЦЕ ПЕРВОЙ СТРОКИ. Я ПРОСТО РЕШИЛ СДЕЛАТЬ ПРОВЕРКУ В ОБЕ СТОРОНУ, НО ЕСЛИ НУЖНА В ОДНУ - ТО СДЕЛАЙТЕ ТАК, НЕ НУЖНА - ОСТАВЬТЕ КАК ЕСТЬ

Answer 2

Вам надо просто понять, есть ли такая трансформация из первой строки во вторую.

Эту трансформацию можно выразить как отношение символ-символ или простым словарем.

Мы просто пройдемся по слову и будем строить словарь пока он имеет смысл. Если найдем, что условие в словаре нарушено, то можно сразу вернть false.

Код на C#

public bool CanConvert(string str1, string str2)
{
    if(str1.Length != str2.Length) return false;
    Dictionary<char, char> map = new Dictionary<char, char>();
    
    for(int i=0; i<str1.Length; i++)
    {
        char c1 = str1[i];
        char c2 = str2[i];
        
        if (map.ContainsKey(c1) && map[c1]!=c2) return false;
        map[c1] = c2;
    }
    
    return true;
}

Проверка

Console.WriteLine(CanConvert("привет","прикол"));
Console.WriteLine(CanConvert("ааббдд","ддббаа"));
Console.WriteLine(CanConvert("абаб","ааах"));

Вывод

True
True
False

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

БЛОГ НА HUSL

Превратить первую строку во вторую, заменяя одни буквы на другие

Ответы (2 шт):