[HackerRank] Append and Delete 字符串增删操作问题

题目地址：Append and Delete | HackerRank

题目大意：

现有两种操作：

Append: 从字符串末端增加一个字符
Delete: 从字符串末端删去一个字符，对空字符串进行删除操作的结果还是空字符串

给定：

1. 两个字符串 s 和 t；
2. 步骤数 k。

判定能否通过上述两种操作，在 k 步骤内将 s 转换为 t？

例子：给定字符串 abc 和字符串 abd，以及步骤数 2。我们可以通过：

Step1: Delete c；
Step2: Append d；

在 2 步骤内实现从 abc 到 abd 的转换。所以本例子结果为：可以。

编程语言：Scala

1. 参考思路

这个题目本身思路不难，但要想将所有情况全部考虑到还是有些困难的。

1.1 情况一：使用 k 步骤恰好实现转换

这种情况很容易想到，只要先通过一次遍历，找到两个字符串从左到右最长的相同子串就可以了。

然后，二者剩余子串的长度之和，即是转换过程中必须进行的步骤。让我们假设这个步骤数为 N。

N 是否等于 k，是最通常的验证情况。

N < k 是肯定不行的，但如果 N > k 是否可行呢？下面我们看看其他一些情况。

让我们假设 N - k = X，即二者的差值。

1.2 情况二：X 为偶数

在经过了 N 步骤之后，此时两个字符串已经完全相等。但步骤数还剩下偶数 X。此时，我们可以通过交替的 Append、Delete 来消耗掉多余的步骤。

比如：abc => abcd => abc => ... => abc。

所以，当 X 为偶数时，例子可是可行的。

1.3 情况三：X 为奇数

那么，当 X 为奇数时，是不是就一定不可行呢？

注意，题目在描述 Delete 方法时，提到了空字符串的情况。也就意味着，我们可以通过将字符串 s 全部删除后，继续删除若干数目，用以抵消 X。

但这样一来，X 的大小就受到了限制。当我们通过 N 步骤，将字符串调节至相同后，如果想通过上述方法抵消差值 X，则意味着 X >= 2 * N，不然 Delete 操作之后，是无法通过 Append 操作复原的。

2. 参考代码

结合上述参考思路，代码不难写出。主要注意对特殊情况的覆盖：

def appendAndDelete(s: String, t: String, k: Int): String = {
    val sLength = s.length
    val tLength = t.length
    val minLength = Math.min(sLength, tLength)
    var done = false
    var index = 0
    while (done == false && index < minLength) {
        if (s(index).equals(t(index)) == false) {
            done = true
        } else {
            index += 1
        }
    }
    val stepCount = (sLength - index) + (tLength - index)
    println(index)
    println(stepCount)
    if (k.equals(stepCount) ||
        ((k - stepCount) > 0 && 0.equals((k - stepCount) % 2)) ||
        k >= stepCount + 2 * index)
        "Yes" else "No"
}

代码 Gist 地址为：Answer of question from https://www.hackerrank.com/challenges/append-and-delete/problem · GitHub