Вопрос о равенстве строк в Scala из интервью по программированию

Этот код занимает O(N) времени и требует всего три целых числа дополнительного пространства:

def solution(a: String, b: String): Boolean = {

  def findNext(str: String, pos: Int): Int = {
    @annotation.tailrec
    def rec(pos: Int, backspaces: Int): Int = {
      if (pos == 0) -1
      else {
        val c = str(pos - 1)
        if (c == '/') rec(pos - 1, backspaces + 1)
        else if (backspaces > 0) rec(pos - 1, backspaces - 1)
        else pos - 1
      }
    }
    rec(pos, 0)
  }

  @annotation.tailrec 
  def rec(aPos: Int, bPos: Int): Boolean = {
    val ap = findNext(a, aPos)
    val bp = findNext(b, bPos)
    (ap < 0 && bp < 0) ||
    (ap >= 0 && bp >= 0 && (a(ap) == b(bp)) && rec(ap, bp))
  }

  rec(a.size, b.size)
}

Задачу можно решить за линейное время с постоянным лишним пространством: если сканировать справа налево, то можно быть уверенным, что /-символы слева от текущей позиции не могут влиять на уже обработанные символы (справа от текущую позицию) в любом случае, поэтому нет необходимости их сохранять. На каждом этапе вам нужно знать только две вещи:

1. Где ты в строю?
2. Сколько символов вы должны выбросить из-за пробелов

Это дает два целых числа для хранения позиций и одно дополнительное целое число для временного хранения количества накопленных возвратов во время вызова findNext. Это в общей сложности три целых числа накладных расходов.

Интуиция

Вот моя попытка сформулировать, почему сканирование справа налево дает вам алгоритм O (1):

Будущее не может влиять на прошлое, поэтому нет необходимости помнить о будущем.

«Естественное время» в этой задаче течет слева направо. Поэтому, если вы сканируете справа налево, вы перемещаетесь «из будущего в прошлое», и поэтому вам не нужно запоминать символы справа от вашего текущего положения.

Тесты

Вот рандомизированный тест, который делает меня уверенным, что решение действительно правильное:

val rng = new util.Random(0)
def insertBackspaces(s: String): String = {
  val n = s.size
  val insPos = rng.nextInt(n)
  val (pref, suff) = s.splitAt(insPos)
  val c = ('a' + rng.nextInt(26)).toChar
  pref + c + "/" + suff
}

def prependBackspaces(s: String): String = {
  "/" * rng.nextInt(4) + s
}

def addBackspaces(s: String): String = {
  var res = s
  for (i <- 0 until 8) 
    res = insertBackspaces(res)
  prependBackspaces(res)
}

for (i <- 1 until 1000) {
  val s = "hello, world"
  val t = "another string"

  val s1 = addBackspaces(s)
  val s2 = addBackspaces(s)
  val t1 = addBackspaces(t)
  val t2 = addBackspaces(t)

  assert(solution(s1, s2))
  assert(solution(t1, t2))
  assert(!solution(s1, t1))
  assert(!solution(s1, t2))
  assert(!solution(s2, t1))
  assert(!solution(s2, t2))

  if (i % 100 == 0) {
    println(s"Examples:\n$s1\n$s2\n$t1\n$t2")
  }
}

Несколько примеров, которые генерирует тест:

Examples:
/helly/t/oj/m/, wd/oi/g/x/rld
///e/helx/lc/rg//f/o, wosq//rld
/anotl/p/hhm//ere/t/ strih/nc/g
anotx/hb/er sw/p/tw/l/rip/j/ng
Examples:
//o/a/hellom/, i/wh/oe/q/b/rld
///hpj//est//ldb//y/lok/, world
///q/gd/h//anothi/k/eq/rk/ string
///ac/notherli// stri/ig//ina/n/g
Examples:
//hnn//ello, t/wl/oxnh///o/rld
//helfo//u/le/o, wna//ova//rld
//anolq/l//twl//her n/strinhx//g
/anol/tj/hq/er swi//trrq//d/ing
Examples:
//hy/epe//lx/lo, wr/v/t/orlc/d
f/hk/elv/jj//lz/o,wr// world
/anoto/ho/mfh///eg/r strinbm//g
///ap/b/notk/l/her sm/tq/w/rio/ng
Examples:
///hsm/y//eu/llof/n/, worlq/j/d
///gx//helf/i/lo, wt/g/orn/lq/d
///az/e/notm/hkh//er sm/tb/rio/ng
//b/aen//nother v/sthg/m//riv/ng

Кажется, работает просто отлично. Итак, я бы сказал, что парень из Google не напортачил, похоже, вполне правильный вопрос.

Вам не нужно создавать вывод, чтобы найти ответ. Вы можете повторить две последовательности одновременно и остановиться на первом различии. Если вы не находите различий и обе последовательности заканчиваются одновременно, они равны, в противном случае они различны.

Но теперь рассмотрим последовательности, подобные этой: 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 достаточно хорош, чтобы вы могли отбрасывать типы в частичной функции внутри вашего foldLeft
• Nil — это идиоматический способ обозначения случая пустого списка.

Бонус:

Перед реализацией своей идеи я имел в виду что-то вроде решения Тима, но я рано начал с сопоставления шаблонов только для символов, и это не подходило, потому что в некоторых случаях требуется количество пробелов. В конце концов, я думаю, что более аккуратный способ написать это — это сочетание сопоставления с образцом и условий if. Ниже приведено мое более длинное оригинальное решение, которое я дал выше, позже было реорганизовано:

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

Если целью является минимальный объем памяти, трудно возражать против итераторов.

def areSame(a :String, b :String) :Boolean = {
  def getNext(ci :Iterator[Char], ignore :Int = 0) : Option[Char] =
    if (ci.hasNext) {
      val c = ci.next()
      if (c == '/')        getNext(ci, ignore+1)
      else if (ignore > 0) getNext(ci, ignore-1)
      else                 Some(c)
    } else None

  val ari = a.reverseIterator
  val bri = b.reverseIterator
  1 to a.length.max(b.length) forall(_ => getNext(ari) == getNext(bri))
}

С другой стороны, при обсуждении принципов FP трудно защищать итераторы, поскольку все они связаны с поддержанием состояния.

Вот версия с одной рекурсивной функцией и без дополнительных классов или библиотек. Это линейное время и постоянная память.

def compare(a: String, b: String): Boolean = {
  @tailrec
  def loop(aIndex: Int, aDeletes: Int, bIndex: Int, bDeletes: Int): Boolean = {
    val aVal = if (aIndex < 0) None else Some(a(aIndex))
    val bVal = if (bIndex < 0) None else Some(b(bIndex))

    if (aVal.contains('/')) {
      loop(aIndex - 1, aDeletes + 1, bIndex, bDeletes)
    } else if (aDeletes > 0) {
      loop(aIndex - 1, aDeletes - 1, bIndex, bDeletes)
    } else if (bVal.contains('/')) {
      loop(aIndex, 0, bIndex - 1, bDeletes + 1)
    } else if (bDeletes > 0) {
      loop(aIndex, 0, bIndex - 1, bDeletes - 1)
    } else {
      aVal == bVal && (aVal.isEmpty || loop(aIndex - 1, 0, bIndex - 1, 0))
    }
  }

  loop(a.length - 1, 0, b.length - 1, 0)
}