时间戳

首页 > 解决方案 > 在 Java 中寻找性能更好的字符串替换解决方案

java - 在 Java 中寻找性能更好的字符串替换解决方案

问题描述

给定一个只能有字母的字符串输入。如果存在 AB、CD、BA、DC 的组合，则应通过删除这些出现并返回结果字符串来转换字符串。例子：

  1. 输入：ABDCC -> 输出：C
  2. 输入：CABABD -> CABD -> CD -> 输出：空字符串 我想出了一个使用字符串替换功能的以下解决方案，但正在寻找更高效或替代的解决方案。有任何想法吗？
public String transformString(String s) {
        HashSet<String> stringsToRemove = new HashSet();
        stringsToRemove.add("AB");
        stringsToRemove.add("BA");
        stringsToRemove.add("CD");
        stringsToRemove.add("DC");
        
        int prevLength = -1;
        while (prevLength != s.length()) {
            prevLength = s.length();
            for (String d : stringsToRemove) {
               s = s.replace(d, "");
            }
        }
        return s;
    }

标签： javastringalgorithmdata-structuresreplace

解决方案

从括号匹配中获取策略并使用堆栈。帮助您入门的解决方案草图：

Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
  if (stack.empty()) {
    stack.push(c);
  }
  else {
    char t = stack.peek();
    if (/* t and c match, such as 'A' and 'B' */) {
      stack.pop();
    }
    else {
      stack.push(c);
    }
  }
}

// Return a string based on what's left in the stack.

显然，这仅在“匹配”没有边缘情况时才有效，例如他们评论中提到的情况 user3386109。

这只会传递输入两次（一次在循环中，一次展开堆栈以构建输出），因此输入大小的线性时间也是如此。

推荐阅读