Предложение алгоритма решения тестового задания?

Question

[danilabot]

Условие задачи
Ограничение времени, с1
Ограничение памяти, МБ64

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

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

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

Выходные данные
В качестве ответа в стандартный вывод программа должна выводить 1 (если превратить можно) или 0 (если превратить нельзя).

Пример 1

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

Пример 2

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

Пример 3

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

Примечания по оформлению решения

При отправке решений на Java необходимо назвать исполняемый класс Main. В решении не нужно указывать пакет.
Для работы со стандартным потоком ввода в JS используйте require('readline'), а для работы со стандартным потоком вывода - console.log(String(data)).

Пример ввода-вывода на JS:

const readline = require('readline'); 
const rl = readline.createInterface(process.stdin, process.stdout); 
rl.on('line', (line) => { // Введенная строка в переменной line, тут можно написать решение console.log(String(result)); 
rl.close(); return; }).on('close', () => process.exit(0));

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

Моё решение:

const readline = require('readline')
const rl = readline.createInterface(process.stdin, process.stdout); 
rl.on('line', (line) => { 
    
    function result(line){
    let arr = line.split(' ');

    let word1 = arr[0].split('');
    let word2 = arr[1].split('');

    if(word1.length != word2.length){
        return 0;
    } else {
        for(let i = 0; i < word1.length; i++){
            for(let j = 0; j < word1.length; j++){
                if (word1[i] == word1[j] && word2[i] != word2[j]){
                    return 0;
                }
            }    
        }
        return 1;
    }
}
    console.log(String(result(line))); 
    rl.close(); 
    return; 
}).on('close', () => process.exit(0));

Собственно вопрос: По результатам ответа HR данная программа не работает на всех тестах, однако на всех вариантах, которые я смог придумать всё работало. Можете предложить другие варианты решения данной задачи?

Comments

[RAX7]

Попробуй так:

function result(str) {
  const [str1, str2] = str.split(' ');
  if (str1.length !== str2.length) return 0;

  const dict = {};
  for (let i = 0; i < str1.length; i++) {
    if (dict[str1[i]] && dict[str1[i]] !== str2[i]) {
      return 0;
    }
    else {
      dict[str1[i]] = str2[i];
    }
  }

  return 1;
}

Answer 1

[Wataru]

Ваше решение не работает на примере "аб аа".

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

Но в ваше решение еще не рассматривает крайний случай - использованы все 33 буквы алфавита и есть надо что-то менять. Тут ответ 0, потому что замены делать никак не получится - после любой замены 2 разные типа букв станут одинаковыми и перемешаются. Разделить их после этого уже не получится.

Если вы эти косяки исправите, ваше решение может не пройти по времени, потому что оно у вас за квадрат. Лучшее решение - пройтись по строкам одновременно одним циклом и запоминать в массиве, индексированном символами, (или мапе), какая буква алфавита во втором слове соответствует букве алфавита в первом слове. Если встречаете противоречие (в массиве уже что-то записано не такое как вы видите сейчас), то ответ 0.

И еще. Не надо разбивать строки через .split(''). В JavaScript можно узнать длину строк и обратиться к i-ому символу не преобразуя в массив.

Answer 2

[twobomb]

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

"абвгдежзийклмнопрстуфхцчшщъыьэюя яюэьыъщшчцхфутсрпонмлкйизжедгвба"

, то должен вернуться 0.
P.S. Крч что-то набыдлокодил, вроде должно работать хотя далеко не самый оптимальный вариант. Ну также можно посмотреть именно вывод замен

function result(line) {
  let arr = line.split(' ');

  let word1 = arr[0].split('');
  let word2 = arr[1].split('');

  if (word1.length != word2.length)
    return 0;
  var abc = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя";

  for (var i = 0; i < word1.length; i++)
    if (!word1.every((e, j) => (e !== word1[i]) || (e == word1[i] && word2[j] == word2[i])))
      return 0;

  var i = 0;
  while (word1.join("") != word2.join("")) {
    if (word1[i] != word2[i]) {
      var repS = word2[i];
      if (word1.join("").indexOf(repS) != -1) {
        var tempAbc = abc.split("").filter(w => word1.join("").indexOf(w) == -1);
        if (tempAbc.length == 0)
          return 0;
        repS = tempAbc.pop();
      }
      word1 = word1.join("").replace(new RegExp(word1[i], "g"), repS).split("");
      console.log(word1)

    }
    i = (i + 1) % word1.length;
  }

  return 1;
}

Comments

[Станислав Некрасов]

А буква ё? На неё же можно заменить

[twobomb]

Станислав Некрасов, Во блин я не руками прописывал, генерил кодом от 1024 + 32, хотя сначала + 33 сделал, но вышло за диапазон, еще и подумал вроде бы букв 33 в алфавите может быть запамятовал что-то... проверил оказывается ё аж 1105 код имеет ...
Респект вам за внимательность!

[Станислав Некрасов]

twobomb, эх... Да, когда буквы имеют не совсем ожидаемые коды, становится не очень... Похоже, у меня решение с ё не будет работать... Но я вроде исправил)