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)，因為我們儲存了臨時字串。