CODEWITHSUNDEEP
algorithmscala
Metadata
Metadata

Reputation: 2083

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

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 ?

Upvotes: 4

Views: 3751

Answers (6)

Harish
Harish

Reputation: 425

Python solution using stack:

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)

Upvotes: 0

Wajid
Wajid

Reputation: 2341

Here's a version in 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

Upvotes: 0

Abhishek Nehe
Abhishek Nehe

Reputation: 55

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

Upvotes: 0

KAMALAKANTA ROUL
KAMALAKANTA ROUL

Reputation: 9

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

In main method, initialize int val =0.

Upvotes: 0

Aakanksha Chopra
Aakanksha Chopra

Reputation: 29

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

Upvotes: 2

jwvh
jwvh

Reputation: 51271

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

Upvotes: 8

Related Questions