How to call a function recursively when using a WHILE loop and break it properly?

Question

I am trying to transform a string by removing a letter A with an adjacent letter B or by removing a letter C toghether with an adjacent letter D.

For example 1, given a string "CBACD", it should be transformed as

CBACD -> CCD -> C

Example 2: given a string "CABABD", it should return nothing as the transformation goes like below:

CABABD -> CABD -> CD -> 

Example 3: "ACBDACBD", There are no corresponding adjacent characters to A & C so the entire string should be returned

"ACBDACBD" -> "ACBDACBD"

I have written the following code to do the operation:

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)
    }
}

The above code works fine for the first iteration which is: CABABD -> CABD For the inputs: ACBDACBD, CBACD, the output is correct but for ACBDACBD, the output is CD. I called the method adjacent before the print statement as below:

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

But this goes to infinite loop and give stackoverflow exception. I am unable to call the method: adjacent recursively so that it can work until the end of the string ? Could anyone let me know how can I properly call the method: adjacent recursively so that the entire string is processed until the end ?

Answer 1

Seems pretty straight forward.

@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

This could be done in Java, as follows :

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);
}