编程访谈中的Scala字符串平等问题

Question

由于我喜欢在Scala中编程,在我的Google采访中,我让他们给我一个Scala /函数式编程风格的问题.我得到的Scala功能样式问题如下:

您有两个由字母字符组成的字符串以及一个表示退格符号的特殊字符.我们将这个退格字符称为"/".当您到达键盘时,键入此字符序列,包括退格/删除字符.要实现的解决方案必须检查两个字符序列是否产生相同的输出.例如,"abc","aa/bc"."abb/c","abcc /","/ abc"和"// abc"都产生相同的输出"abc".因为这是一个Scala /函数编程问题,所以必须以惯用的Scala风格实现您的解决方案.

我写了下面的代码(可能不是我写的,我只是关闭内存).基本上我只是线性地通过字符串,将字符前置到列表,然后我比较列表.

def processString(string: String): List[Char] = {
  string.foldLeft(List[Char]()){ case(accumulator: List[Char], char: Char) =>
    accumulator match {
      case head :: tail => if(char != '/') { char :: head :: tail } else { tail }
      case emptyList => if(char != '/') { char :: emptyList } else { emptyList }
    }
  }
}

def solution(string1: String, string2: String): Boolean = {
  processString(string1) == processString(string2)
}

到现在为止还挺好？然后他询问时间复杂度,我回答线性时间(因为你必须处理每个字符一次)和线性空间(因为你必须将每个元素复制到一个列表中).然后他让我在线性时间内做,但是有恒定的空间.我想不出一种纯粹功能性的方法.他说尝试在Scala集合库中使用一个函数,如"zip"或"map"(我明确地记得他说过"zip"这个词).

这就是事情.我认为在没有任何可变状态或副作用的情况下,在恒定空间内进行它是不可能的.就像我认为他弄乱了这个问题.你怎么看？

你可以在线性时间内解决它,但是空间恒定吗？

Answer 1

此代码需要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

似乎工作得很好.所以,我会说谷歌家伙没有搞砸,看起来像一个完全有效的问题.

Answer 2

您不必创建输出来查找答案.您可以同时迭代这两个序列并停止第一个差异.如果你发现没有差异并且两个序列同时终止,它们是相同的,否则它们是不同的.

但现在考虑这样的序列: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 是引用空列表案例的惯用方法

奖金:

在实现我的想法之前,我有一些类似Tim的解决方案,但是我很早就开始使用关于字符的模式匹配而且它不适合,因为有些情况需要退格数量.最后,我认为编写它的一种更简洁的方式是模式匹配和条件的混合.下面是我较长的原始解决方案,我上面提到的是重构的解决方案:

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