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 ?

You have s.slice(i+2, s.length), shouldn't you assign the result of that to a variable? — smac89
– smac89, Commented Nov 27, 2019 at 7:11
I'm just saying that line by itself does nothing, so you either need to remove it or make use of the result — smac89
– smac89, Commented Nov 27, 2019 at 7:26
Actually I have tried to use it in the first 'IF' of the while loop as: i += 2 solution(s.slice(i, s.length)) But I still see the same output for CABABD -> CD — Metadata
– Metadata, Commented Nov 27, 2019 at 9:52
Also @jwvh answer is good but I want to try my attempt first and as a last resort I will use the answer. — Metadata
– Metadata, Commented Nov 27, 2019 at 9:54

jwvh · Accepted Answer · 2019-11-27 07:50:59Z

8

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

edited Nov 27, 2019 at 7:50

answered Nov 27, 2019 at 7:21

jwvh

51.3k7 gold badges42 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Anvesh Over a year ago

can you provide same answer in python

Aakanksha Chopra · Accepted Answer · 2022-01-25 16:45:46Z

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

answered Jan 25, 2022 at 16:45

Aakanksha Chopra

291 bronze badge

Comments

KAMALAKANTA ROUL · Accepted Answer · 2022-02-19 02:54:00Z

0

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.

answered Feb 19, 2022 at 2:54

KAMALAKANTA ROUL

93 bronze badges

1 Comment

devilpreet Over a year ago

You can probably loop length/2 times, since we remove two chars at a time.

Abhishek Nehe · Accepted Answer · 2023-01-21 18:16:50Z

0

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

answered Jan 21, 2023 at 18:16

Abhishek Nehe

551 silver badge9 bronze badges

1 Comment

Wajid Over a year ago

I don't understand what's wrong with this solution ? Why are people downvoting it ?

Wajid · Accepted Answer · 2023-06-16 12:19:54Z

0

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

edited Jun 16, 2023 at 12:19

answered Jun 16, 2023 at 12:05

Wajid

2,3511 gold badge23 silver badges29 bronze badges

Comments

Harish · Accepted Answer · 2023-08-04 16:35:20Z

0

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)

answered Aug 4, 2023 at 16:35

Harish

4257 silver badges23 bronze badges

Collectives™ on Stack Overflow

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

6 Answers 6

1 Comment

Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

Comments

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related