这可以只用递归完成吗？

给定一个字符串，返回递归一个“干净”的字符串，其中属于同一相邻字符已经减少为单个字符。所以“yyzzza”产生“yza”。

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

我可以使用循环解决这个问题，但这是不允许的，因为这个问题应该这样来使用递归解决。有没有办法解决这个问题，而不使用循环，只使用递归？没有全局变量，没有循环。我甚至想过在参数中编码一些信息，但我认为这也会作弊。

我以前的程序没有while循环，我只能得到一半的答案。基本上，当我用字符串参数调用我的函数时，我检查了前两个字符。如果它们是相同的，我会返回字符并再次用一个小于两个字符的字符串调用该函数。然而，一串3或4个相同的连续字符总是会击败我的算法。

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

}

来源

2012-12-01 toto

是的，只用递归就可以解决这个问题。我会给你提示，你应该创建一个辅助方法，它有两个参数：前一个字符和剩余的字符串。 –

我的问题是下面的，有没有什么办法来解决这个问题，而无需使用一个循环，并只使用递归。没有全局变量，没有循环。

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

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（ “你好”）→ “直升机”， “直升机” OK
stringClean（ “XXabcYY”）→ “XabcY” “XabcY” OK
stringClean（ “112ab445”）→ “12ab45” “12ab45” OK
stringClean（ “你好簿记员”）→ “直升机Bokeper” “直升机Bokeper” OK
其他测试OK

来源

2012-12-01 23:48:34

当然，最后发送字符。这就是我应该做的。非常感谢！ – toto

我的问题是下面的，有没有什么办法来解决这个问题，而无需使用一个循环，并只使用递归。没有全局变量，没有循环。

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

提示：

最喜欢的 “刁钻” 问题递归这需要一个额外的参数。
将问题看作是在每个阶段过滤字符串的第一个字符。
输入字符串的第一个字符是一个特殊情况...

来源

2012-12-01 23:40:59

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-26 15:46:15 Sarath

这可以只用递归完成吗？

回答

相关问题