Учитывая 2 строки и целое число k, преобразовать одну строку в другую ровно за k шагов

Question

Я решаю проблему на странице «HackerRank», в частности, проблему под названием «Добавить и удалить», но не могу исправить все случаи.

https://www.hackerrank.com/challenges/append-and-delete/problem

"У вас есть строчная буква английского алфавита sh алфавита c букв. Вы можете выполнить два типа операций над строкой:

Добавить строчную букву английского языка английского языка sh алфавита c буква до конца строки. Удалить последний символ в строке. Выполнение этой операции над пустой строкой приводит к пустой строке. При условии целого числа, и двух строк, и, определить, можно ли преобразовать выполнив в точности те же операции, что и над. Если это возможно, выведите Да. В противном случае выведите №

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

Описание функции

Завершите функцию appendAndDelete в редакторе ниже. Он должен возвращать строку, либо Да, либо Нет.

appendAndDelete имеет следующие параметры:

s: начальная строка t: искомая строка k: целое число, представляющее число операций ".

int cont = 0;
        int limite = 0;


        if (s.length() < t.length()){
            limite += s.length();
        } else if (s.length() >= t.length()){
            limite += t.length();
        }

        for (int i = 0; i < limite; i++){

            if (s.charAt(i) != t.charAt(i)){

                cont += 2;

            }

        }

        int diferen = 0;

        if (s.length() != t.length()){

            diferen += (Math.abs(t.length() - s.length()));

        } 

        cont += diferen;

        if(cont <= k){

            return "Yes";

        } else {
            return "No";
        }

Answer 1

Введение

Чтобы определить проблему в вашем коде, давайте упростим ее.

Упростим limite Расчет

Для вычисления значения limite вы используете Блок if/else, как показано ниже:

if (s.length() < t.length()){
    limite += s.length();
} else if (s.length() >= t.length()){
    limite += t.length();
}

Однако, поскольку ваш limite всегда равен 0 перед этим блоком, и то, что вы ищете - это длина самой короткой строки, вы можете просто заменить это с помощью:

int limite = Math.min(s.length(), t.length());

Упрощение diferen вычисление

Опять же, вам не нужен блок if для вычисления diferen - если обе строки имеют одинаковую длину, то diferen - это просто 0, и это то, что Math.abs(t.length() - s.length()) также даст.

Итак, вместо этого:

int diferen = 0;
if (s.length() != t.length()) {
    diferen += (Math.abs(t.length() - s.length()));
}

Вы можете просто иметь одну строку:

int diferen = (Math.abs(t.length() - s.length()));

Лучшие имена переменных

Ваш имена переменных типа diferen или cont или limite сбивают с толку. Вместо этого вы можете переименовать эти переменные в absLengthDifference, operationCount и commonLength.

Ваш упрощенный код

static String appendAndDelete(String s, String t, int k) {
    int operationCount = 0;

    int shorterStringLength = Math.min(s.length(), t.length());

    for (int i = 0; i < commonLength; i++) {
        if (s.charAt(i) != t.charAt(i)) {
            operationCount += 2;
        }
    }

    int absLengthDifference = (Math.abs(t.length() - s.length()));
    operationCount += absLengthDifference;

    if(operationCount <= k) {
        return "Yes";
    } 

    return "No";
}

Поиск логических ошибок

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

Давайте рассмотрим ввод, как показано ниже:

ab

bb

2

Ваша программа вынесет положительный приговор, поскольку operationCount будет 2, но operationCount <= 2. Таким образом, это неверно, потому что для преобразования ab в bb с использованием операций в задаче мы должны выполнить следующее:

'ab' -> 'a' | единственный способ добраться до 'a' - удалить 'b'

'a' -> '' | единственный способ исправить 'a' - сначала удалить его

'' -> 'b' | и затем добавьте 'b'

'b' -> 'bb' | наконец, снова добавьте 'b'

Как видите, нам потребовалось 4 операций для достижения желаемого результата, а не 2. Следовательно, приведенный ниже блок неверен:

for (int i = 0; i < commonLength; i++) {
    if (s.charAt(i) != t.charAt(i)) {
        operationCount += 2;
    }
}

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

Кроме того, if(operationCount <= k) неверно, поскольку число операций должно быть точно k.

Решение для исправления

1. Первое, что нужно понять, это если k больше или равно сумме длин строк, тогда ответ равен Yes. Мы можем удалить все символы из исходной строки s и продолжить удаление символа из пустой строки 0 или более раз, а затем добавить символы из целевой строки t.
2. В противном случае, если найти длина commonLength общей строки для обоих, тогда мы можем преобразовать s в t с шагом s.length() + t.length() - 2*commonLength. Однако это значение minOperationCount не может быть больше, чем k по очевидным причинам. Кроме того, если оно меньше k, тогда k - minOperationCount должно быть кратно 2. Если это не так, то можно выполнить преобразование в точности k шагов.

Код

// Complete the appendAndDelete function below.
static String appendAndDelete(String s, String t, int k) {
    int totalLength = s.length() + t.length();
    if (totalLength <= k) {
        return "Yes";
    }

    int commonLength = 0;
    for (int i = 0; i <  Math.min(s.length(), t.length()); i++) {
        if (s.charAt(i) != t.charAt(i)) {
            break;
        }
        commonLength++;
    }  
    int minOperationCount = totalLength - 2 * commonLength;

    if(minOperationCount <= k && ((k - minOperationCount) % 2 == 0)) {
        return "Yes";
    } 

    return "No";
}