1

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

}
4

4 回答 4

6

我的问题如下，有没有办法在不使用循环且只使用递归的情况下解决这个问题。没有全局变量，没有循环。

回答：是的。这很简单。试试下面：

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

您的 CodingBat 结果如下：

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
其他测试 OK

于 2012-12-01T23:48:34.453 回答
1

我的问题如下，有没有办法在不使用循环且只使用递归的情况下解决这个问题。没有全局变量，没有循环。

答案是“是的，这是可能的”。

提示：

  • 像大多数“棘手的”递归问题一样，这需要一个额外的参数。
  • 将问题视为在每个阶段过滤字符串的第一个字符。
  • 输入字符串的第一个字符是特殊情况...
于 2012-12-01T23:40:59.210 回答
0 
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;
    }
}
于 2013-10-26T15:46:15.827 回答
0

这是我的答案

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

}
于 2019-11-12T11:36:21.507 回答