CODEWITHSUNDEEP
javarecursion
toto
toto

Reputation: 900

Can this be done with recursion only?

I am stuck on this CodingBat recursion problem:

Given a string, return recursively a "cleaned" string where adjacent chars that are the same have been reduced to a single char. So "yyzzza" yields "yza". 

stringClean("yyzzza") → "yza"
stringClean("abbbcdd") → "abcd"
stringClean("Hello") → "Helo"

I can solve it using loops, but this is not allowed since the problem is supposed so be solved using recursion. Is there any way to solve this problem without using a loop and using only recursion? No global variables, no loops. I even thought of encoding some information in the parameter but that would be cheating too I think.

My previous program had no while loop, and I could only get half of the answers right. Basically, when I called my function with the string parameter, I checked the first 2 characters. If they were the same, I would return the character and call the function again with a string two characters smaller. A string of 3 or 4 of the same consecutive characters would always defeat my algorithm however.

public String stringClean(String str) {

    if (str.length() == 0)
        return "";

    if (str.length() > 1) {

    int counter = 1;


      char a = str.charAt(0);
      char b = str.charAt(1);

       if (a == b)
       {
          while (str.length() > 1)
          {
             a = str.charAt(0);
             b = str.charAt(1);

             if (a != b) break;

             counter++;
             str = str.substring(1);


          }

           return a + stringClean( str.substring(1) ) ;
       }

    }

    return str.charAt(0) + stringClean (str.substring(1) );

}

Upvotes: 1

Views: 1770

Answers (4)

Varad Paralikar
Varad Paralikar

Reputation: 81

Here is my answer

public String stringClean(String str) {
  if(str.isEmpty()) return "";
  if(str.length()==1)return str;

  if(str.length() > 1 && !str.substring(0,1).equals(str.substring(1,2)))
    return str.substring(0,1) + stringClean(str.substring(1));

  return ""+stringClean(str.substring(1));

}

Upvotes: 0

Sarath
Sarath

Reputation: 1496

public String stringClean(String str) {
    if (str == null) {
        return null;
    } else if (str.length() > 1) {
        String k = str.substring(0, 1);
        if (str.charAt(0) == str.charAt(1)) {
            String tmp = stringClean(str.substring(2));
            return k + stringClean(tmp);
        } else {
            return k + stringClean(stringClean(str.substring(1)));
        }
    } else {
        return str;
    }
}

Upvotes: 0

Yogendra Singh
Yogendra Singh

Reputation: 34367

My question is the following, is there any way to solve this problem without using a loop and using only recursion. No global variables, no loops.

Answer: Yes. It is very simple. Try below:

 public String stringClean(String str) {
      if (str.length() == 0)
            return "";
      if (str.length() == 1)
            return str;

      if(str.charAt(0) == str.charAt(1)){
         return stringClean(str.substring(1));   
      }else{
        return str.charAt(0)+ stringClean(str.substring(1));
      }    
    }

Your CodingBat results in below:

stringClean("yyzzza") → "yza" "yza" OK
stringClean("abbbcdd") → "abcd" "abcd" OK
stringClean("Hello") → "Helo" "Helo" OK
stringClean("XXabcYY") → "XabcY" "XabcY" OK
stringClean("112ab445") → "12ab45" "12ab45" OK
stringClean("Hello Bookkeeper") → "Helo Bokeper" "Helo Bokeper" OK
other tests OK

Upvotes: 6

Stephen C
Stephen C

Reputation: 718788

My question is the following, is there any way to solve this problem without using a loop and using only recursion. No global variables, no loops.

The answer is "yes it is possible".

Hints:

  • Like most "tricky" recursive problems this requires an extra parameter.
  • Think of the problem as filtering the first character of the string at each stage.
  • The first character of the input string is a special case ...

Upvotes: 1

Related Questions