-5

Complete the following method which takes a string, and for each repeating sequence of characters in the string, removes all but one of them. For example, given the input string "AAAABCCDDDDAACCCCCC", the method should return "ABCDAC".

YOUR CODE MUST BE RECURSIVE. Do not use any loops (while, do/while, or for). Do not declare any variables outside of the method. You may declare local variables inside the method.

public static String eliminateRepeats (String s)
{
4

3 回答 3

1 
public class Recurse
{
    public static void main( String args[] )
    {
        System.out.println( recurse( "AAAABCCDDDDAACCCCCC" ) );
    }

    private static String recurse( String s )
    {
        if ( s == null || s.equalsIgnoreCase("") )
        {
            return "";
        }
        else if ( s.length() > 1 )
        {
            if ( !s.substring( 0 , 1 ).equalsIgnoreCase( s.substring( 1 , 2 ) ) )
            {
                return s.substring( 0 , 1 ) + recurse( s.substring( 1 ) );
            }

            return recurse( s.substring( 1 ) );
        }
        else
        {
            return s.substring( 0 , 1 );
        }
    }
}
于 2012-04-30T15:55:18.790 回答
1

这里的诀窍是你需要一个循环来解决这个问题，所以你只需通过使用越来越小的字符串部分递归调用该方法来伪造一个循环。

没有办法将工作分成更小的部分，就像使用递归时通常所做的那样（例如将字符串分成两半）。您只需一次处理一个字符，然后使用字符串的其余部分调用该方法。

C# 中的示例：

public static string EliminateRepeats(string s) {
  return
    s.Length == 1 ?
      s
    :
      (s[0] != s[1] ? s.Substring(0, 1) : "")
      + EliminateRepeats(s.Substring(1));
}

（受 Jonathan Paynes 代码启发的代码。）

于 2012-04-30T16:23:52.567 回答
0 
// use a default value for the lastchar for the first char, 
// which is impossible to meet in an regular string
def concentrate (s: String, lastchar: Char = 0) : String = {
    // recursive methods always need to know when it is enough
    if (s.length == 0) s else 
    if (s(0) == lastchar) concentrate (s.substring (1), lastchar) else 
    s(0) +  concentrate (s.substring (1), s(0)) }

concentrate ("AAAABCCDDDDAACCCCCC")

这是一个尾递归变体：

@tailrec 
def concentrate (s: String, carry:String = "", lastchar: Char = 0) : String = {
    if (s.length == 0) carry else 
    if (s(0) == lastchar) concentrate (s.substring (1), carry, lastchar) else 
    concentrate (s.substring (1), carry + s(0), s(0)) }

它在最后一个位置有递归调用，因为生成的字符串会动态粘合在一起，并作为参数传递。在 Scala 中，编译器可以对此进行优化，使其运行速度几乎与带有可变变量的循环一样快，而且它不会破坏堆栈——即使对于很长的字符串也是如此。

于 2012-05-01T20:44:39.153 回答