scala - scala laziness - 如何在这个回文搜索中摆脱 return 语句？

Question

上下文：在大量文本中找到最长的回文。

这里有两种解决方案——一种是“返回”（完全脱离嵌套函数），另一种是糟糕的“纯”答案。我如何编写具有第一个性能的纯解决方案？

  def isPalindrome(str: String) : Boolean = str.reverse == str

  def longestPalindrome(haystack : String) : String = {
    (haystack.length to 1 by -1).foreach{ substrSize =>
      haystack.sliding(substrSize).foreach{ substr =>
        if(isPalindrome(substr))
          return substr
      }
    }
    ""
  }

  def longestPalindrome2(haystack : String) : String = {
    val x = for {
      substrSize <- haystack.length to 1 by -1
      substr <- haystack.sliding(substrSize)
    } yield (substr -> isPalindrome(substr))
    x.find(_._2 == true).map(_._1).getOrElse("")
  }

Answer 1

您的问题似乎是如何在不使用return. 一种方法是创建一个非严格view的Range. 这是一个例子，

def palindromeStream(haystack : String) = {
  for {
    substrSize <- (haystack.length to 1 by -1).view
    substr <- haystack.sliding(substrSize)
    if isPalindrome(substr)
  } yield substr
}

val x = palindromeStream("a canal") // Palindromes not yet computed
x.headOption                        // Compute the first one: Some(ana)
x.toSet                             // Compute the rest: Set(n, ana, a, " ", l, c)

你也可以考虑Range.toStream。

Answer 2

您可以稍微提高第二种方法的性能：

def longestPalindrome3(haystack: String): String =
    (for {
      substrSize <- haystack.length to 1 by -1
      substr <- haystack.sliding(substrSize)
      if (isPalindrome(substr))
    } yield substr).headOption.getOrElse("")