Backspace 字符串比较 Leetcode 问题

Question

我对Leetcode上的以下问题有疑问：

给定两个字符串 S 和 T，return 如果在空文本编辑器中输入它们时它们相等。 # 表示一个后退space字符。

示例 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) 时间内解决吗space?

我的回答：

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) space 的复杂性。

我不知道如何继续进行下去，已经为此工作了整整 2 个小时..

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

谢谢！ :)

Answer 1

请记住，N <= 200，您的问题更可能是线性系数，而不是算法复杂度。 O(N) space 对此无关紧要；总共只有 400 个字符，space 不是问题。您有六个 regex 匹配项，其中两个是多余的。更重要的是，regex 对此类特定应用程序的处理速度很慢。

为了提高速度，放弃 regex 的东西，然后用一种直接的、暴力的方式来做这个：运行按顺序遍历每个字符串，将后面的 space 应用为合适的。例如，将后面的 space 和前面的字母都更改为 spaces。在检查结束时，删除所有 space 以创建新字符串。对 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可以简化。我把它留作 reader.

的练习

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;
    }
}

Backspace 字符串比较 Leetcode 问题

Backspace String Compare Leetcode Question

regex

ruby

algorithm

space-complexity