Backspace String Сравнить 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 </p>

1 <= T.length <= 200 </p>

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 ваша проблема, скорее всего, будет линейным коэффициентом, а не сложностью алгоритма. <strong>O (N) пространство для этого несущественно; всего 400 символов, пространство не проблема. У вас есть шесть regex матчей, два из которых являются избыточными. Что еще более важно, regex - медленная обработка для такого специфического c приложения.

Для скорости, отбросьте материал 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

Давайте посмотрим на более длинный string.

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 будет отсутствовать 398351 знак фунта в s, плюс почти равное число из других символов, удаленных знаками фунта, мы ожидаем, что 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;
    }
}