删除字符串中彼此相邻的一对字符

Question

在一次面试中，我遇到了一个问题，我找不到动态输入的逻辑。

输入：abbcaddaee

如果给出此输入，我们必须删除一对字符，例如 abbcaddaee。粗体值将被删除，输出为 acaa，然后我们也必须为此做同样的事情，然后 acaa。最终输出为ac.

同样必须进行 n 次迭代才能删除这些相同的对 char。

输入：aabbbcffjdddd→aabbbcffjdddd→bcj

Answer 1

我会在这里使用正则表达式替换：

String input = "aabbbcffjdddd";
String output = input.replaceAll("(.)\1", "");
System.out.println(output);  // bcj

正则表达式模式 (.) 匹配后跟相同字符一次的任何单个字符。我们用空字符串替换这些匹配项，有效地删除它们。

Answer 2

在下面的解决方案中，我使用递归的方法给了你想要的结果。

对于模式：

1st Capturing Group (.)
. matches any character (except for line terminators)
 matches the same text as most recently matched by the 1st capturing group

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    private static Pattern p = Pattern.compile("(.)\1");

    public static void main(String[] args) {
        System.out.println(removePairChar("abbcaddaee"));
        System.out.println(removePairChar("aabbbcffjdddd"));
    }

    public static String removePairChar(String input) {
        Matcher matcher = p.matcher(input);
        boolean matchFound = matcher.find();
        if(matchFound) {
            input = input.replaceAll(p.pattern(), "");
            return removePairChar(input);
        }
        return input;
    }

}

输出：

ac
bcj

Answer 3

您可以使用 regexp 和单个 do-while 循环:

String str = "abbcaddaee";

do {
    System.out.println(str);
} while (!str.equals(str = str.replaceAll("(.)\1", "")));

输出：

abbcaddaee
acaa
ac

解释：

regexp (.)\1 - 任何字符后跟相同的字符；
str = str.replaceAll(...) - 删除所有重复项并替换当前字符串；
!str.equals(...) - 检查当前字符串自身的 不平等 ，但不重复。

^{另请参阅：}

Answer 4

基本思路是使用Stack。在这种情况下，我们将具有 O(n) 复杂度，而不是 while + replaceAll

遍历字符代码，如果堆栈中不存在字符代码则将其推送
如果栈头等于当前字符码弹出

import java.util.Optional;
import java.util.Stack;

public class Main {

    public static void main(final String... params) {
        System.out.println(Main.normalize("abbcaddaee"));
        System.out.println(Main.normalize("aabbbcffjdddd"));
    }

    private static String normalize(final String input) {
        final int length = Optional.ofNullable(input).map(String::length).orElse(0);
        if (length < 2) {
            return input;
        }

        Stack<Integer> buf = new Stack<Integer>();
        input.codePoints().forEach(code -> {
            if (buf.isEmpty() || buf.peek() != code) {
                buf.push(code);
            } else {
                buf.pop();
            }
        });

        return buf.stream().collect(
            StringBuilder::new,
            StringBuilder::appendCodePoint,
            StringBuilder::append).
            toString();
    }
}

删除字符串中彼此相邻的一对字符

Remove a pair of chars in a string next to each other

java

string

replace

char

duplicates