给定2个字符串和整数k，以精确的k步将一个字符串转换为另一个字符串

Question

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

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

“您有一个小写英文字母字符串。您可以对该字符串执行两种类型的操作：

在字符串的末尾附加一个小写英文字母。删除字符串中的最后一个字符。对空字符串执行此操作将导致空字符串。给定一个整数和两个字符串，以及，确定是否可以通过对执行上述操作来转换为。如果可能，请打印Yes。否则，打印编号。

例如，字符串和。我们的移动次数。要转换为，我们首先删除移动中的所有字符。接下来，我们按顺序添加每个字符。在移动中，您将拥有匹配的字符串。如果有更多可用的移动，它们可以通过对空字符串执行多次删除来消除。如果少于移动，我们将无法成功创建新字符串。

功能描述

在下面的编辑器中完成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

为了发现代码中的问题，让我们简化它。

要计算极限值，请使用如下所示的if/else块：

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

但是，由于在该块之前，您的限制始终为0，并且您要查找的是最短字符串的长度，因此您可以简单地将其替换为：

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

同样，你不需要任何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()));

您的变量名称，如differen、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

“ab”-

“a”

''

“b”-

如您所见，我们花了4操作来实现所需的结果，而不是2。因此，下面的块是错误的：

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

仅仅添加2是不够的。如果发现不匹配，则必须从末尾删除所有字符才能找到它（如示例所示）。

此外，if（操作计数

1. 首先要意识到的是，如果k大于或等于字符串长度之和，那么答案是Yes。我们可以从原始字符串s中删除所有字符，并不断从空字符串0中删除一个字符或多次，然后从目标字符串t中附加字符。
2. 否则，如果找到两者的公共字符串的长度通用长度，那么我们可以在s.length（）t.length（）-2*通用长度步骤中将s转换为t。但是，由于明显的原因，该值minOPationCount不能大于k。此外，如果它小于k，则k-minOPationCount必须是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";
}