Scala 中的“无重复字符的最长子串”

Question

我已经解决了没有重复字符的最长子串问题使用滑动窗口技术：

def lengthOfLongestSubstring(s: String): Int = {

  case class Acc(chars: Set[Char], left: Int, len: Int)
  s.zipWithIndex.scanLeft(Acc(Set(), 0, 0)) { case (acc, (c, right)) =>

    def moveLeftBoundary(chars: Set[Char], left: Int): (Set[Char], Int) =
      if (chars.contains(c)) moveLeftBoundary(chars - s(left), left + 1) else (chars, left)

    val (chars, left) = moveLeftBoundary(acc.chars, acc.left)
    Acc(chars + c, left, right - left + 1)

  }.map(_.len).max
}

解决方案被接受并且不是很长但是由于索引和内部函数看起来有点笨拙。你能在 Scala 中提出一个更简单的解决方案吗？

Answer 1

我不关心 fp 或不关心性能敏感的代码。实际上pure fp style code always slower in my experience.

我们开始：

def lengthOfLongestSubstring(s: String): Int = {
    def rec(start: Int, end: Int, size: Int, visited: Array[Int]): Int = 
        if (end >= s.length) size
        else {
            val newStart = start.max(visited(s(end).toInt) + 1)
            visited(s(end).toInt) = end
            rec(newStart, end+1, size.max(end-newStart+1), visited)
        }

    rec(0, 0, 0, Array.fill(128)(-1))
}

Answer 2

接受的答案让我意识到我应该在访问过的字符和它们的索引之间保留一个映射，而不是像我那样只保留一组访问过的字符。所以我可以删除

moveLeftBoundary

来简化解决方案并提高性能。

def lengthOfLongestSubstring(s: String): Int = {

  case class Acc(left: Int, len: Int, visited: Map[Char, Int])

  s.zipWithIndex.scanLeft(Acc(left = 0, len = 0, Map())) { case (acc, (c, right)) =>
    val left = acc.visited.get(c).map(_ + 1.max(acc.left)).getOrElse(acc.left)
    val len = right - left + 1
    val visited = acc.visited + (c -> right)
    Acc(left, len, visited)
  }.map(_.len).max
}

这个解决方案更短，更易读。性能更好但仍然不是很好。