后置字符串比较Leetcode问题

Question

关于Leetcode的以下问题，我有一个问题：

给定两个字符串S和T，如果它们是相等的，则在空文本编辑器中输入这两个字符串时返回。#表示退格字符。

示例1：

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

示例2：

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

例3：

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

例4：

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:

1 <= S.length <= 200

1 <= T.length <= 200

S和T只包含小写字母和“#”字符。

后续行动：

你能在O(N)时间和O(1)空间中求解吗？

我的答案是：

def backspace_compare(s, t)
   if (s.match?(/[^#[a-z]]/) || t.match?(/[^#[a-z]]/)) || (s.length > 200 || t.length > 200)
    return "fail"
   else
    rubular = /^[\#]+|([^\#](\g<1>)*[\#]+)/
    if s.match?(/#/) && t.match?(/#/)
      s.gsub(rubular, '') == t.gsub(rubular, '')
    else
      new_s = s.match?(/#/) ? s.gsub(rubular, '') : s
      new_t = t.match?(/#/) ? t.gsub(rubular, '') : t
      new_s == new_t
    end
  end
end

它在终端中工作，并传递给出的示例，但是当我以leetcode提交它时，它告诉我超过了时间限制。我试着把它缩短到：

    rubular = /^[\#]+|([^\#](\g<1>)*[\#]+)/
      new_s = s.match?(/#/) ? s.gsub(rubular, '') : s
      new_t = t.match?(/#/) ? t.gsub(rubular, '') : t
      new_s == new_t

但也有同样的错误。

到目前为止，我认为我的代码实现了O(n)时间，因为只有两个三元操作符，总体上是O(n)。我做了3个作业和一个比较，所以我相信这满足了O(1)空间的复杂性。

我不知道该怎么做，我已经花了两个小时的时间。

请指出我的代码中是否有任何错误，以及我如何能够修复它。

谢谢！:)

Answer 1

请记住，对于N <= 200，您的问题更可能是线性系数，而不是算法复杂性。O(N)空间对此不重要；只有400个字符，空间不是问题。您有六个regex匹配，其中两个是冗余的。更重要的是，对于这样一个特定的应用程序，regex处理速度很慢。

为了加快速度，放下regex的内容，并执行以下一种简单的、蛮力的方法:按顺序遍历每个字符串，并酌情应用这些后置空间。例如，将backspace和前面的字母更改为空格。在检查结束时，删除生成新字符串时的所有空格。用S和T来做这件事；比较一下那些是否相等。

Answer 2

最简单的方法是从字符串的末尾开始，直到开始：

def process(str)
  n = 0
  str.reverse.each_char.with_object('') do |c,s|
    if c == '#'
      n += 1
    else
      n.zero? ? (s << c) : n -= 1
    end
  end.reverse
end

​

%w|ab#c ad#c ab## c#d# a##c #a#c a#c b|.each_slice(2) do |s1, s2|
  puts "\"%s\" -> \"%s\", \"%s\" -> \"%s\"  %s" %
    [s1, process(s1), s2, process(s2), (process(s1) == process(s2)).to_s]
end

"ab#c" -> "ac", "ad#c" -> "ac"  true
"ab##" -> "",   "c#d#" -> ""    true
"a##c" -> "c",  "#a#c" -> "c"   true
"a#c"  -> "c",  "b"    -> "b"   false

让我们看一个更长的字符串。

require 'time'

alpha = ('a'..'z').to_a
  #=> ["a", "b", "c",..., "z"]

s = (10**6).times.with_object('') { |_,s|
  s << (rand < 0.4 ? '#' : alpha.sample) }
  #=> "h####fn#fjn#hw###axm...#zv#f#bhqsgoem#glljo"

s.size
  #=> 1000000
s.count('#')
  #=> 398351

看看需要多长时间处理。

require 'time'

start_time = Time.now
(u = process(s)).size
  #=> 203301 
puts (Time.now - start_time).round(2)
  #=> 0.28 (seconds)

u #=> "ffewuawhfa...qsgoeglljo" 

由于u将丢失s中的398351磅标志，加上几乎相同数量的其他字符被磅号移除，所以我们希望u.size大约是：

10**6 - 2 * s.count('#')
  #=> 203298 

事实上，u.size #=> 203301，这意味着，在最后，203301 - 203298 #=> 3庞德符号无法从s中删除一个字符。

事实上，process可以简化。我把它留给读者做练习。

Answer 3

class Solution {
    public boolean backspaceCompare(String s, String t) {
        try {

            Stack<Character> st1 = new Stack<>();
            Stack<Character> st2 = new Stack<>();

            st1 = convertToStack(s);
            st2 = convertToStack(t);

            if (st1.size() != st2.size()) {
                return false;
            } else {
                int length = st1.size();
                for (int i = 0; i < length; i++) {
                    if (st1.peek() != st2.peek())
                        return false;
                    else {
                        st1.pop();
                        st2.pop();
                    }
                    if (st1.isEmpty() && st2.isEmpty())
                        return true;

                }
            }
        } catch (Exception e) {
            System.out.print(e);
        }

        return true;

    }

        public Stack<Character> convertToStack(String s){
        Stack<Character> st1 = new Stack<>();

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) != '#') {
                st1.push(s.charAt(i));
            } else if (st1.empty()) {
                continue;
            } else {
                st1.pop();
            }

        }
        return st1;
    }
}