使用 WHILE 循环时如何递归调用函数并正确中断它?

Question

我试图通过删除带有相邻字母 B 的字母 A 或删除带有相邻字母 D 的字母 C 来转换字符串。

例如 1，给定一个字符串"CBACD"，它应该转换为

CBACD -> CCD -> C

示例 2：给定一个字符串"CABABD"，它应该不返回任何内容，因为转换如下所示：

CABABD -> CABD -> CD -> 

示例 3："ACBDACBD"，A 和 C 没有相应的相邻字符，因此应返回整个字符串

"ACBDACBD" -> "ACBDACBD"

我编写了以下代码来执行此操作：

object RemoveCharsABCD {
val s = scala.io.StdIn
def adjacent(s: String): String = {
val charSet = ArrayBuffer("AB","BA","CD","DC")
var i   = 0
var ret:String = ""
while(i < s.length-1) {
if(charSet.contains(s"${s.charAt(i)}${s.charAt(i+1)}")) {
s.slice(i+2, s.length)
i += 2
if(i == s.length-1) ret = s"$ret${s.charAt(i).toString}"
} else {
ret = s"$ret${s.charAt(i).toString}"
i += 1
if(i == s.length-1) ret = s"$ret${s.charAt(i).toString}"
}
}
println("Ret: " + ret)
ret
}
def main(args: Array[String]): Unit = {
println("Enter a String: ")
var s = scala.io.StdIn.readLine().toString
adjacent(s)
}
}

上面的代码适用于第一次迭代，即：CABABD -> CABD对于输入：ACBDACBD，CBACD，输出是正确的，但对于ACBDACBD，输出是CD。 我在 print 语句之前调用了相邻的方法，如下所示：

if(ret.length >= 2) {
adjacent(ret)
}
println("Ret: " + ret)

但这进入无限循环并给出stackoverflow例外。 我无法调用该方法：递归adjacent，以便它可以工作到字符串的末尾？ 谁能告诉我如何正确调用该方法：递归相邻，以便处理整个字符串直到最后？

Answer 1

看起来很简单。

@annotation.tailrec 
def adjacent(s: String): String = {
val next = s.replaceAll("AB|BA|CD|DC", "")
if (s == next) s else adjacent(next)
}
adjacent("CBACD")     //res0: String = C
adjacent("CABABD")    //res1: String =
adjacent("ACBDACBD")  //res2: String = ACBDACBD

Answer 2

这可以在Java中完成，如下所示：

public static String remove(String str)
{
if (str == null) {
return null;
}
char[] chars = str.toCharArray();
int i = 0, k = 0;
while (i < str.length())
{
if (    chars[i] == 'B' && (k > 0 && chars[k - 1] == 'A') ||
chars[i] == 'A' && (k > 0 && chars[k - 1] == 'B') ||
chars[i] == 'C' && (k > 0 && chars[k - 1] == 'D') || 
chars[i] == 'D' && (k > 0 && chars[k - 1] == 'C'))
{
--k;
++i;
}   
else {
chars[k++] = chars[i++];
}
}
return new String(chars).substring(0, k);
}

Answer 3

private static String stringAfterRemove(String str,int val,int lengthOfString) {

String nStr = str.replaceAll("CD", "").replaceAll("DC", "").replaceAll("AB", "").replaceAll("BA", "");
if(val==lengthOfString)
return str;
return stringAfterRemove(nStr,++val,lengthOfString);
}

在 main 方法中，初始化 int val =0。

Answer 4

public static String solution(String str) {
String next = str.replaceAll("AB|CD|DC|BA", "");
if(str.equals(next))
return str;
else
return solution(next);
}

Answer 5

这是 Kotlin 中的一个版本：

fun solution(input: String): String {
val result = input.replace("AB|CD|DC|BA".toRegex(), "")
return if (result == input)
input
else
solution(result)
}

solution("CBACD")     //output = C
solution("CABABD")    //output =
solution("ACBDACBD")  //output = ACBDACBD

Answer 6

使用堆栈的Python解决方案：

def solution(S):
stack = []
for i, val in enumerate(S):
if stack and ((stack[-1] == "A" and val == "B") or (stack[-1] == "B" and val == "A") or
(stack[-1] == "C" and val == "D") or (stack[-1] == "D" and val == "C")):
stack.pop()
else:
stack.append(val)        
return "".join(stack)