Java程序递归删除所有相邻重复字符

---

题目描述：给定一个长度为N（N为整数）的字符串str，其中包含字母数字字符。我们需要递归删除所有相邻的重复字符，以便结果字符串不包含任何相邻的重复字符。

我们可以使用递归或迭代方法来解决这个问题。这里，我们首先从字符串的左端移除相邻的重复元素。之后，我们递归地从字符串的右端移除相邻的重复元素。

示例场景1

Input: str1 = "tuttor";
Output: res = tuor

相邻的重复字符是tt，它将从字符串中移除。

示例场景2

Input: str2 = "adbccbd";
Output: res = a

第一步，它将从字符串中移除cc，字符串将变成adbbd。之后，bb将被移除，结果字符串将是add。接下来，移除dd，字符串将变成a。

示例场景3

Input: str3 = "abcd";
Output: res = abcd

字符串不包含任何相邻的重复字符。因此，输出字符串与输入字符串相同。

使用递归

在这种方法中，我们将进行函数的递归调用以删除相邻的字符串字符。请遵循以下步骤：

• 步骤1 -如果字符串长度为0或1，则返回相同的字符串，因为它不包含任何重复项。

• 步骤2 -如果前两个字符相同，则该函数将移除开头所有该字符的出现，并使用剩余的字符串递归调用自身。

• 步骤3 -如果第一个字符是唯一的，则它将对从第二个字符开始的子字符串递归调用自身。

• 步骤4 -递归调用之后，函数检查原始字符串的第一个字符是否与递归调用的结果的第一个字符匹配。如果匹配，则它将从结果中移除第一个字符。

• 步骤5 -否则，将原始字符串的第一个字符附加到递归调用的结果中。

示例

在这里，我们在删除字符串右半部分的相邻字符后，将结果字符串存储到临时字符串中。

import java.io.*;
import java.util.*;

public class Main {
   static String recursivelyRemove(String alpha, char last_char) {
      // base case
      if (alpha.length() == 0 || alpha.length() == 1)
         return alpha;
      // Remove duplicate characters from the left, and then recursively call for the
      // right part
      if (alpha.charAt(0) == alpha.charAt(1)) {
         last_char = alpha.charAt(0);
         while (alpha.length() > 1 && alpha.charAt(0) == alpha.charAt(1))
            alpha = alpha.substring(1, alpha.length());
         alpha = alpha.substring(1, alpha.length());
         return recursivelyRemove(alpha, last_char);
      }
      // First character will be unique, so remove duplicates from another part
      String temp = recursivelyRemove(alpha.substring(1, alpha.length()), last_char);
      // If the first character is the same as the first character of the original string, remove it.
      if (temp.length() != 0 && temp.charAt(0) == alpha.charAt(0)) {
         last_char = alpha.charAt(0);
         return temp.substring(1, temp.length());
      }
      // If the temp string is empty, and last_char is equal to the first character of the original, return temp.
      if (temp.length() == 0 && last_char == alpha.charAt(0))
         return temp;
      // append first character with temp and return.
      return (alpha.charAt(0) + temp);
   }
   static String duplicateRemoval(String str) {
      return recursivelyRemove(str, '\0');	
   }
   public static void main(String args[]) {
      String str1 = "tuttor";
      System.out.println("The string after recursively removing the adjacent duplicates is - " + duplicateRemoval(str1));
   }
}

运行上述代码后，将产生以下结果：

The string after recursively removing the adjacent duplicates is - tuor

时间复杂度- T(N) = T(N−K) + O(K) ~ O(N*K)，因为我们从字符串中删除了第一个相同的字符。

空间复杂度- O(N)，用于在临时字符串中存储字符串。

使用迭代和递归

在这种方法中，迭代遍历字符串以查找相邻的重复字符，然后在剩余部分调用递归函数以删除这些重复字符。

示例

让我们来看一个Java程序，它实际上实现了上述方法。

import java.io.*;
import java.util.*;

public class Main {
   static String duplicateRemoval(String alpha, char ch) {
      // base case
      if (alpha == null || alpha.length() <= 1) {
         return alpha;
      }
      int p = 0;
      while (p < alpha.length()) {
         // If characters at index p and q are the same
         if (p + 1 < alpha.length() && alpha.charAt(p) == alpha.charAt(p + 1)) {
            // Finding first q same characters
            int q = p;
            while (q + 1 < alpha.length() && alpha.charAt(q) == alpha.charAt(q + 1)) {
               q++;
            }
            // store the last removed character
            char last_removed = p > 0 ? alpha.charAt(p - 1) : ch;
            // Remove duplicate from remaining part
            String tempStr = duplicateRemoval(alpha.substring(q + 1, alpha.length()), last_removed);
            alpha = alpha.substring(0, p);
            int len = alpha.length(), l = 0;
            // If the last char of the alpha string and the first char of tempStr are the same, remove them until they match
            while (tempStr.length() > 0 && alpha.length() > 0
                        && tempStr.charAt(0) == alpha.charAt(alpha.length() - 1)) {
               // Make iterations until tempStr has the first character the same as the last character of
               while (tempStr.length() > 0 && tempStr.charAt(0) != ch
                        && tempStr.charAt(0) == alpha.charAt(alpha.length() - 1)) {
                  tempStr = tempStr.substring(1, tempStr.length());
               }
               // remove last character from alpha
               alpha = alpha.substring(0, alpha.length() - 1);
            }               
            alpha = alpha + tempStr; // append alpha to tempStr
            p = q; // updating p-value
         } else {
            p++;
         }
     }
     return alpha;
   }
   public static void main(String args[]) {
      String str1 = "tuttorppoi";
      System.out.println(
                "The string after recursively removing the adjacent duplicates is - " + duplicateRemoval(str1, ' '));
   }
}

运行上述代码后，将显示以下结果：

The string after recursively removing the adjacent duplicates is - tuoroi

时间复杂度- O(N)，因为我们遍历了字符串。

空间复杂度- O(N)，因为我们存储了临时字符串。