Вам не нужно создавать вывод, чтобы найти ответ. Вы можете повторять две последовательности одновременно и останавливаться на первой разнице. Если вы не найдете никакой разницы, и обе последовательности завершаются одновременно, они равны, в противном случае они разные.
Но теперь рассмотрим такие последовательности: aaaa/// для сравнения с a. Вам нужно использовать 6 элементов из левой последовательности и один элемент из правой последовательности, прежде чем вы сможете утверждать, что они равны. Это означает, что вам нужно будет хранить как минимум 5 элементов в памяти, пока вы не убедитесь, что все они удалены. Но что, если вы перебрали элементы с конца? Затем вам нужно будет просто подсчитать количество возвратов, а затем просто проигнорировать столько элементов, сколько необходимо в левой последовательности, без необходимости хранить их в памяти, поскольку вы знаете, что они не будут присутствовать в конечном выводе. Используя эти два совета, вы можете получить O(1) памяти.
Я пробовал, и, кажется, работает:
def areEqual(s1: String, s2: String) = {
def charAt(s: String, index: Int) = if (index < 0) '#' else s(index)
@tailrec
def recSol(i1: Int, backspaces1: Int, i2: Int, backspaces2: Int): Boolean = (charAt(s1, i1), charAt(s2, i2)) match {
case ('/', _) => recSol(i1 - 1, backspaces1 + 1, i2, backspaces2)
case (_, '/') => recSol(i1, backspaces1, i2 - 1, backspaces2 + 1)
case ('#' , '#') => true
case (ch1, ch2) =>
if (backspaces1 > 0) recSol(i1 - 1, backspaces1 - 1, i2 , backspaces2 )
else if (backspaces2 > 0) recSol(i1 , backspaces1 , i2 - 1, backspaces2 - 1)
else ch1 == ch2 && recSol(i1 - 1, backspaces1 , i2 - 1, backspaces2 )
}
recSol(s1.length - 1, 0, s2.length - 1, 0)
}
Некоторые тесты (все пройдено, дайте мне знать, если у вас есть несколько крайних случаев):
// examples from the question
val inputs = Array("abc", "aa/bc", "abb/c", "abcc/", "/abc", "//abc")
for (i <- 0 until inputs.length; j <- 0 until inputs.length) {
assert(areEqual(inputs(i), inputs(j)))
}
// more deletions than required
assert(areEqual("a///////b/c/d/e/b/b", "b"))
assert(areEqual("aa/a/a//a//a///b", "b"))
assert(areEqual("a/aa///a/b", "b"))
// not enough deletions
assert(!areEqual("aa/a/a//a//ab", "b"))
// too many deletions
assert(!areEqual("a", "a/"))
PS: всего несколько заметок о самом коде:
- Вывод типа Scala достаточно хорош, так что вы можете отбрасывать типы в функции part внутри вашей
foldLeft
Nil - идиоматический способ ссылки на случай пустого списка
Бонус:
Я имел в виду что-то вроде решения Тима перед тем, как реализовать мою идею, но я рано начал с сопоставления с образцом только для символов, и это не подходило, потому что в некоторых случаях требуется количество обратных пробелов. В конце концов, я думаю, что более точный способ написать это - сочетание соответствия шаблонов и условий. Ниже мое более длинное оригинальное решение, которое я дал выше, было переделано laater:
def areEqual(s1: String, s2: String) = {
@tailrec
def recSol(c1: Cursor, c2: Cursor): Boolean = (c1.char, c2.char) match {
case ('/', '/') => recSol(c1.next, c2.next)
case ('/' , _) => recSol(c1.next, c2 )
case (_ , '/') => recSol(c1 , c2.next)
case ('#' , '#') => true
case (a , b) if (a == b) => recSol(c1.next, c2.next)
case _ => false
}
recSol(Cursor(s1, s1.length - 1), Cursor(s2, s2.length - 1))
}
private case class Cursor(s: String, index: Int) {
val char = if (index < 0) '#' else s(index)
def next = {
@tailrec
def recSol(index: Int, backspaces: Int): Cursor = {
if (index < 0 ) Cursor(s, index)
else if (s(index) == '/') recSol(index - 1, backspaces + 1)
else if (backspaces > 1) recSol(index - 1, backspaces - 1)
else Cursor(s, index - 1)
}
recSol(index, 0)
}
}