java - 如何改进以下算法以递归地删除字符串中从右到左相邻的重复字符？

Question

问题陈述是递归地删除字符串中的重复项。 例如:abcddaacg -> abccg-> abg

现在我实现的算法是这样的:

保留2个指针(i和j)。我总是 < j。 str[j] 始终是元素 str[i] 比较以删除重复项。因此，当 j = 6 和 i = 5 时，我将它们都替换为 '\0'，然后将 j 更新为 7 (c)。然后当 j = 4 和 i = 3(都是 d，j 得到更新，原因是 str[4] != str[6]，因此 j = i，变成 j = 4)，我们将它们都更新为“\0”。

当我将 j 更新为 7 时，我的问题在于下一步。为此，我必须搜索下一个不是“\0”的字符。这就是使它成为 O(n^2) 实现的原因。我怎样才能做得更好？ O(n)

代码如下:

static void remDups (String input) {

    char [] str = input.toCharArray();
    int j = input.length()-1;

    int i = input.length()-2;

    while (i >= 0){

        if (str[i] == str[j]) {
            str[i] = '\0';
            str[j] = '\0';
            j++;
            while (str[j] == '\0' && j < str.length) {
                j++;
            }
        } else {
            j = i;
        }
        i--;
    }

    i = 0;
    while (i < input.length()) {
        if (str[i] != '\0')
            System.out.print(str[i]);
        i++;
    }
} 

Answer 1

这是一个迭代解决方案，它使用 stack 并删除 char[] 上的相邻重复项，因为自 String 以来它们更易于使用对象是不可变的。

在每次迭代中:

• 如果需要删除任何相邻的重复项，请使用 boolean 标志进行跟踪。

• 将相邻元素不相等的元素压入堆栈。

• 如果我们找到相等的相邻元素，当它们相等时递增计数器(因为您可能有两个以上的相等相邻元素)更新标志以表明需要删除相邻的重复元素

• 否则我们就完成了

• 如果标志被激活，我们将用存储在堆栈中的非重复项覆盖我们的 char[] 并重复循环直到没有重复项被删除。

代码如下:

static char[] removeAdjDups(char[] data) {
    if (data == null) {
        return null;
    }

    Stack<Character> stack = new Stack<Character>();
    boolean removal = true; // flag keeping track if any dups were removed
    char[] temp;
    while (removal) {
        /* set removal to false */
        removal = false;

        /* push elements that don't have equal adjacents onto the stack */
        for (int i = 1; i < data.length; i++) {
            if (data[i - 1] != data[i]) {
                stack.push(data[i - 1]);
            } else {
                while (i < data.length && data[i - 1] == data[i]) {
                        i++;
                }
                /* if we found equal adjacents, activate the removal flag */
                removal = true;
            }

            if (i == data.length - 1) {
                stack.push(data[i]);
            }
        }

        /* if dups were removed
           store the array with removed adjacent dups into original data */
        if (removal) {
            temp = new char[stack.size()];
            for (int i = temp.length - 1; i >= 0; i--) {
                temp[i] = stack.pop();
            }
            data = temp;
        }
    }

    return data;
}

public static void main(String[] args) {
    String str = "abcddaacg";
    System.out.println(removeAdjDups(str.toCharArray()));
}

输出:

abg