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

68de4m5k 于 2023-04-12 发布在 Scala

关注(0)|答案(2)|浏览(137)

我使用sliding window技术解决了Longest Substring Without Repeating Characters问题：

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中提出一个更简单的解决方案吗？

scala

来源：https://stackoverflow.com/questions/75905705/longest-substring-without-repeating-characters-in-scala

2条答案

按热度按时间

g9icjywg1#

我不关心是否使用fp来处理性能敏感的代码。实际上，根据我的经验，纯fp风格的代码总是比没有纯fp的代码慢。
开始了

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

赞(0）回复(0）举报 2023-04-12

rqcrx0a62#

accepted answer让我意识到我应该在访问过的字符和它们的索引之间保持一个Map，而不是像我那样只保留一组访问过的字符。所以我可以删除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
}

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

赞(0）回复(0）举报 2023-04-12

我来回答

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

2条答案

相关问题

热门标签

最新问答