递归计算字符串中的字符数，并将“eu”视为单个字符

Question

我是Java新手，正尝试弄清楚如何计算给定字符串中的字符数，并将"eu"这样的两个字符组合视为一个单一字符，同时仍然将所有其他字符视为一个字符。

而我想使用递归来实现。

考虑以下示例。

输入：

"geugeu"

抱歉，我只能用英语回答你的问题。

4   // g + eu + g + eu = 4

当前输出：

2

我一直在尝试很多次，但似乎仍然无法弄清楚如何正确实现它。

我的代码：

public static int recursionCount(String str) {
    if (str.length() == 1) {
        return 0;   
    }
    else {
        String ch = str.substring(0, 2);
        if (ch.equals("eu") {
            return 1 + recursionCount(str.substring(1));
        }
        else {
            return recursionCount(str.substring(1));
        }
    }
}

- ScubaDivingGoldFish

---

当 geugeu 只有两个 eu 时，计数为4是如何实现的？代码按预期工作。 - Nikhil

额外的eu是我的错误，对不起。但我需要代码来计算所有字符，但上面列出的4个特殊情况需要作为一个单词计数。因此，“geugeu”在字符串中需要计算为4个字符。 - ScubaDivingGoldFish

然后你必须返回“2 + recursion...”，因为该字符串有两个数字。 - Christian

在这种情况下，在您的if块中使用2 + recursionCount（str.substring（1））; - Ashish Patil

Answer 1

这篇文章想要统计一个字符串中的所有字符数量，但是对于相邻的字符"ae"，"oe"，"ue"和"eu"，应被视为一个单一字符，只计算一次。

下面的代码可以实现这一功能:

public static int recursionCount(String str) {
    int n;
    n = str.length();
    if(n <= 1) {
        return n; // return 1 if one character left or 0 if empty string.
    }
    else {
        String ch = str.substring(0, 2);
        if(ch.equals("ae") || ch.equals("oe") || ch.equals("ue") || ch.equals("eu")) {
            // consider as one character and skip next character
            return 1 + recursionCount(str.substring(2));
        }
        else {
            // don't skip next character
            return 1 + recursionCount(str.substring(1));
        }
    }
}

- Nikhil

Answer 2

递归解释

为了使用递归来解决特定任务，您需要深入了解递归的工作原理。

首先要记住的是，每个递归解决方案都应该（明确或隐含地）包含两个部分：基本情况和递归情况。

让我们仔细看一下它们：

• 基本情况 - 表示一个简单的边缘情况（或一组边缘情况），即递归应该终止的情况。这些边缘情况的结果是预先知道的。对于此任务，基本情况 是给定的 字符串为空，由于没有东西可以计数，返回值 应为 0。这足以使算法工作，其他输入的结果应从 递归情况 中推导出来。

• 递归情况 - 是方法的一部分，在其中进行递归调用并且主要逻辑驻留。每个递归调用最终都会触及 基本情况 并开始构建其返回值。

在递归情况下，我们需要检查给定的字符串是否以特定字符串（如"eu"）开头。为此，我们不需要生成子字符串（请记住对象创建是昂贵的）。相反，我们可以使用方法{{link1：String.startsWith()}}，该方法检查提供的前缀字符串的字节是否与此字符串开头处的字节匹配（提醒：从Java 9开始，String由一组字节支持，并且每个字符根据字符编码用一个或两个字节表示），我们也不需要关心字符串的长度，因为如果字符串比前缀短，则startsWith()将返回false。

实现

话虽如此，以下是实现的样子：

public static int recursionCount(String str) {
    if(str.isEmpty()) {
        return 0;
    }

    return str.startsWith("eu") ?
        1 + recursionCount(str.substring(2)) : 1 + recursionCount(str.substring(1));
}

注意：除了能够实现解决方案之外，您还需要评估其时间和空间复杂度。

在这种情况下，因为我们每次调用都创建一个新字符串，时间复杂度是二次的O(n^2)（提醒：创建新字符串需要分配内存来复制原始字符串的字节）。最坏情况下的空间复杂度也将是O(n^2)。

有一种方法可以在每次调用时不生成新字符串，以线性时间O(n)递归地解决这个问题。为此，我们需要引入第二个参数-当前索引，并且每个递归调用应该将此索引向前推进1或2（我不会实现这个解决方案，留给OP/读者作为练习）。

此外

此外，这里有一个简洁而简单的非递归解决方案，使用String.replace()函数:

public static int count(String str) {
    
    return str.replace("eu", "_").length();
}

如果您需要处理多个字符组合（列在问题的第一个版本中），您可以使用正则表达式与 String.replaceAll()：

public static int count(String str) {
    
    return str.replaceAll("ue|au|oe|eu", "_").length();
}

- Alexander Ivanchenko