java - 给定 2 个字符串和整数 k，只需 k 步将一个字符串转换为另一个字符串

Question

我正在解决“HackerRank”页面上的一个问题，特别是名为“追加和删除”的问题，但我无法使所有情况都正确。

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

"You have a string of lowercase English alphabetic letters. You can perform two types of operations on the string:

Append a lowercase English alphabetic letter to the end of the string. Delete the last character in the string. Performing this operation on an empty string results in an empty string. Given an integer, , and two strings, and , determine whether or not you can convert to by performing exactly of the above operations on . If it's possible, print Yes. Otherwise, print No.

For example, strings and . Our number of moves, . To convert to , we first delete all of the characters in moves. Next we add each of the characters of in order. On the move, you will have the matching string. If there had been more moves available, they could have been eliminated by performing multiple deletions on an empty string. If there were fewer than moves, we would not have succeeded in creating the new string.

Function Description

Complete the appendAndDelete function in the editor below. It should return a string, either Yes or No.

appendAndDelete has the following parameter(s):

s: the initial string t: the desired string k: an integer that represents the number of operations".

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 block 如下:

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

但是，自从您的 limite总是0在此 block 之前，您要查找的是最短字符串的长度，您可以简单地将其替换为:

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

简化 diferen计算

再说一次，你不需要任何 if block 来计算您的 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' | the only way to get to 'a' is to remove 'b'

'a'  -> ''  | the only way to correct 'a' is to remove it first

''  -> 'b'  | and then append 'b'

'b' -> 'bb' | finally, append 'b' again

如您所见，我们花了 4操作以达到期望的结果，而不是 2 。因此，下面的 block 是错误的:

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两者的公共(public)字符串，那么我们可以转换 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";
}