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

在这个问题中，我们需要从字符串中删除所有相邻重复的字符。我们可以使用递归或迭代的方法来解决这个问题。在这里，首先需要从字符串的左侧部分删除相邻重复的元素。之后，我们需要递归地从字符串的右侧部分删除相邻重复的字符。

问题陈述 − 我们已经给出了长度为N的字符串str，其中包含字母数字字符。我们需要递归地删除所有相邻重复的字符，使得结果字符串不包含任何相邻重复的字符。

示例

输入

str1 = "tuttor"

输出

tuor

说明 − 我们从字符串中删除了相邻的 ‘tt’。

输入

str1 = "adbccbd"

输出

a

解释 −

• 在第一步中，它将从字符串中移除’cc’，字符串将变为’adbbd’

• 之后，我们需要从字符串中移除’bb’，结果字符串将变为’add’。

• 接下来，我们需要移除’dd’，字符串将变为’a’。

输入

str1 = ‘abcd’

输出

‘abcd’

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

方法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字符串中删除第一个字符。

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)。

方法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字符串。

示例

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)，因为我们存储了临时字符串。