@goalrazor

Есть задача на JAVA — нет ответа. Как решить задачу?

Дали вот такое проверочное задание. Проверяется оно автоматически на закрытых тестовых данных, но я всегда получаю ответ "неверное решение". То есть видимо не учел какой-то кейс, который может существовать. Подскажите решение или хотя бы кейс, который я не учёл.

Условие задачи

Ограничение времени, с 1
Ограничение памяти, МБ 64
Общее число попыток отправки 15

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

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

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

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

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

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

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

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        String twoLines = scanner.nextLine();
        System.out.println(isEqual(twoLines));
    }
  
 public static String getFreeSymbol(String first, String second) {
        int symbolInt = 'а';
        while (first.contains(String.valueOf((char) symbolInt)) || second.contains(String.valueOf((char) symbolInt))) {
            symbolInt++;
        }
        return String.valueOf((char) symbolInt);
    }

    public static int isEqual(String targetString) {
        targetString = targetString.toLowerCase();
        String[] lines = targetString.split(" ", 2);

        String firstString = lines[0];
        String secondString = lines[1];
        if (firstString.length() != secondString.length()) {
            return 0;
        }
        return isEqual(firstString, secondString);
    }

    public static String check(String firstString, String secondString, String findSymbol, String replaceSymbol, int index, int secondIndex, int i) {
        if ((secondIndex = secondString.indexOf(findSymbol, secondIndex + 1)) > -1) {
            if (firstString.charAt(secondIndex) != secondString.charAt(secondIndex)) {
                if (firstString.charAt(index) == firstString.charAt(secondIndex)) {
                    String freeSymbol = getFreeSymbol(firstString, secondString);
                    firstString = firstString.replaceAll(replaceSymbol, freeSymbol);
                    findSymbol = firstString.substring(i, i + 1);
                } else {
                    if (firstString.charAt(index) == secondString.charAt(index)) {
                        return null;
                    } else {
                        String freeSymbol = getFreeSymbol(firstString, secondString);
                        firstString = firstString.replaceAll(replaceSymbol, freeSymbol);
                    }
                }
            }
        }else{
            findSymbol = secondString.substring(index, index+1);
            String anchorSymbol = firstString.substring(index, index+1);

            do {
                String symbol = firstString.substring(index, index+1);
                if( !symbol.equals(anchorSymbol) ){
                    return null;
                }
                index++;
            } while ((index = secondString.indexOf(findSymbol, index)) > -1);

        }
        return firstString;
    }

    public static int isEqual(String firstString, String secondString) {

        boolean[] isCheck = new boolean[firstString.length()];
        for (int i = 0; i < isCheck.length; i++) {
            String findSymbol = firstString.substring(i, i + 1);
            String replaceSymbol = secondString.substring(i, i + 1);

            if (isCheck[i]) {
                continue;
            }
            int index = i;
            int secondIndex = i;
            String rez = check(firstString, secondString, findSymbol, replaceSymbol, index, secondIndex, i);
            if (rez == null) {
                return 0;
            }else{
                firstString = rez;
            }

            do {
                firstString = firstString.replaceFirst(findSymbol, replaceSymbol);
                isCheck[index] = true;
                index++;
            } while ((index = firstString.indexOf(findSymbol, index)) > -1);
        }
        String result = firstString;
        if (result.equals(secondString)) {
            return 1;
        } else {
            return 0;
        }
    }

  
}
  • Вопрос задан
  • 497 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
У вас сильно наворочено - много где можно ошибиться. Какие-то indexOf() используете кучу раз, хотя можно просто сравнивать символы через CharAt(), субстиринги везде. Советую переписать ваше решение с нуля, искать в нем ошибки невозможно.

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

Нужно только проверить, что символы на одинаковых местах одинаковые или разные в обоих строчках. Ну, или эквивалентно - что для каждого символа предыдущий такой же в обоих строках на одинаковом расстоянии. Проще всего завести 2 map из символа в позицию. Пройтись по двум строкам параллельно и убедиться, что предыдущие вхождения этих символов в строках на одной и той же позиции (или их нет) и обновить записи в map.

Что-то вроде этого (читайте как псевдокод, я джаву не особо знаю):
public static int isEqual(String firstString, String secondString) {
  int used = 0;
  int[] first = new int[256], second = new int[256];
  if (firstString == secondString) return 1;
  if (firstString.length() != secondString.length()) return 0;
  for (i = 0; i < firstString.lengt(); ++i) {
    int ch1 = Character.getNumericValue(firstString.charAt(i));
    int ch2 = Character.getNumericValue(secondString.charAt(i));
    if (first[ch1] == 0) {
      used++;
    }
    if (first[ch1] != second[ch2]) return 0;
    first[ch1] = i+1;  // +1, потому что изначальные 0 означают "символ не встречался"
    second[ch2] = i+1; 
  }
  if (used == 33) return 0;
  return 1;


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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы