Backspace字符串比较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 <=长度<= 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）空间的复杂性。

我不知道如何进行此操作，已经进行了2个小时的研究。

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

谢谢！ ：）

Answer 1

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

为了提高速度，请放下regex东西，然后执行一种简单而又蛮力的方法：依次遍历每个字符串，并适当地应用退格键。例如，将退格键和前一个字母都更改为空格。检查结束后，删除所有空格以创建新字符串。对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。我把它留给读者练习。