极客笔记Java 递归地删除所有相邻重复字符
在这个问题中，我们需要从字符串中删除所有相邻重复的字符。我们可以使用递归或迭代的方法来解决这个问题。在这里，首先需要从字符串的左侧部分删除相邻重复的元素。之后，我们需要递归地从字符串的右侧部分删除相邻重复的字符。
问题陈述 − 我们已经给出了长度为N的字符串str，其中包含字母数字字符。我们需要递归地删除所有相邻重复的字符，使得结果字符串不包含任何相邻重复的字符。
示例
输入
输出
说明 − 我们从字符串中删除了相邻的 ‘tt’。
输入
输出
解释 −
- 在第一步中，它将从字符串中移除’cc’，字符串将变为’adbbd’
-
之后，我们需要从字符串中移除’bb’，结果字符串将变为’add’。
-
接下来，我们需要移除’dd’，字符串将变为’a’。
输入
输出
解释 − 字符串不包含任何相邻重复项。因此，输出字符串与输入字符串相同。
方法1
在这种方法中，我们将递归调用函数来删除相邻的字符串字符。
步骤
步骤 1 − 如果字符串长度为0或1，则返回相同的字符串，因为它不包含任何重复项。
步骤 2 − 如果第一个字符与第二个字符相同，则将字符串的第一个字符赋值给“last_char”变量，因为我们需要从字符串中删除第一个字符。
步骤 3 − 使用循环，从字符串的开头删除所有相同的字符。
步骤 4 − 递归调用函数以从字符串中删除相邻的字符。
步骤 5 − 然后，第一个字符将是唯一的。因此，对从第1个索引开始的字符串调用recursivelyRemove（）函数，并将返回的值存储在temp变量中。
步骤 6 − 如果“temp”字符串的第一个字符与“alpha”字符串的第一个字符相同，则从temp字符串中删除第一个字符并返回它。
步骤 7 − 如果temp字符串为空，并且“last_char”变量的值等于“alpha”字符串的第一个字符，则返回“temp”字符串。
步骤 8 − 返回连接alpha字符串的第一个字符和完整temp字符串的结果字符串。
示例
在“temp”字符串中，我们得到了在字符串右侧删除相邻字符后的结果字符串。可能“temp”字符串的第一个字符和alpha字符串的第一个字符相同。因为我们需要连接alpha和temp字符串的第一个字符，所以如果我们得到相邻的元素，我们需要从temp字符串中删除第一个字符。
输出
时间复杂度 - 当我们从字符串中删除第一个相同的字符时，T(N) = T(N-K) + O(K) ~ O(N*K)。
空间复杂度 - 为了存储临时字符串，复杂度为O(N)。
方法2
我们将使用循环来迭代地删除重复元素。然而，我们还将调用递归函数来从不同的字符串部分中删除重复的相邻元素。
步骤
步骤1 - 如果字符串为空或长度等于1，则返回字符串本身。
步骤2 - 将变量’p’初始化为0，并进行迭代，直到’p’小于字符串长度。
步骤3 - 使用嵌套循环从字符串开头删除相同的字符。同时更新’last_removed’变量。
步骤4 - 现在，再次调用duplicateRemoval()函数，从剩余的字符串中删除重复的相邻元素。将返回值存储在’tempStr’字符串中。
步骤5 - 从alpha中获取长度为p的子字符串，因为它不包含任何相邻重复的元素。
步骤6 - 如果”tempStr”字符串的起始字符相同，我们需要删除这些字符，因为我们需要连接alpha和”tempStr”字符串。
步骤7 - 如果alpha字符串的最后一个字符与”tempStr”字符串的第一个字符相匹配，则删除alpha字符串的最后一个字符。
步骤8 - 将alpha与tempStr合并，并通过将q赋值给p来更新p的值。
步骤9 - 最后，返回alpha字符串。
示例
输出
时间复杂度 − O(N)，因为我们遍历了字符串。
空间复杂度 − O(N)，因为我们存储了临时字符串。