递归计算字符串中的字符并"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));
}
}
}

Answer 1

OP想要计算字符串中的所有字符，但相邻字符"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));
}
}
}

Answer 2

递归解释

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

您需要记住的第一件事是，每个递归解决方案都应该(显式或隐式(包含两部分：基本情况和

递推情况让我们仔细看看它们：

• 基本情况-表示简单边情况(或一组边情况(的部分，即递归应终止的情况。这些边缘病例的结果是事先已知的。对于此任务，基本情况

是指给定的字符串为空，并且由于没有任何可计数的内容，返回值应为0。这足以使算法工作，其他输入的结果应该从递归情况中导出。

Recursive case-是方法中进行递归调用和主逻辑所在的部分。每个递归调用最终都会命中的基本情况，并生成其返回值。

在递归的情况下，我们需要检查给定的字符串是否从"eu"这样的特定字符串开始。为此，我们不需要生成子字符串(请记住，创建对象是有代价的(。相反，我们可以使用方法String.startsWith()，该方法检查提供的前缀字符串的字节是否与该字符串开头的字节匹配，该字符串是chipper(提醒：从Java 9开始String由一个字节数组支持，每个字符由一个或两个字节表示，具体取决于字符编码(，并且我们也不关心字符串的长度因为如果字符串短于前缀CCD_ 6将返回CCD_。

实施

也就是说，以下是实现的样子：

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