具有forloop的scalal回文功能

Question

想知道与Scala等效的Java回文函数，在scala中编写具有多个变量的forloop非常棘手

class Solution {
  public boolean isPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
        i++;
      }
      while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
        j--;
      }

      if (i < j && Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
        return false;
    }

    return true;
  }
}

我能够在scala中为回文编写代码，但是在上述解决方案中空间复杂度为O（1），而下一个具有O（N）

def Ispalindrome(inpt:Option[String]):Boolean ={
  inpt match {
      case Some(inpt)=> {
        val sLetters=inpt.toLowerCase().filter(c=>c.isLetterOrDigit)
        (sLetters==sLetters.reverse)
      }
      case None => false
      }
    }

Answer 1

如果您确实想要循环，则可以执行此操作。空间复杂度是常数/ O（1），因为您仅有的变量是i，j，a和b。时间复杂度的O（n），与Java版本相同。

Answer 2

@scala.annotation.tailrec
def isPalindrome(s: String, i: Int, j: Int): Boolean = {
  if (i >= j) return true
  val c = s.charAt(i)
  if (!(c.isLetter || c.isDigit)) return isPalindrome(s, i + 1, j)
  val d = s.charAt(j - 1)
  if (!(d.isLetter || d.isDigit)) return isPalindrome(s, i, j - 1)
  if (c == d) isPalindrome(s, i + 1, j - 1)
  else false
}
def isPalindrome(s: String): Boolean = isPalindrome(s, 0, s.length)

两者的输出都是

false
true
true
true

for

println(isPalindrome("blaisjdlfkasdjf"))
println(isPalindrome("raceca_+r"))
println(isPalindrome("raccar"))
println(isPalindrome("racecar"))

链接到Scastie：https://scastie.scala-lang.org/oTetGkfsQ5OLUowTylghFw

编辑：The recursive method不带return关键字，可能会引起问题，如@Luis MiguelMejíaSuárez所说：

def isPalindrome(s: String, i: Int, j: Int): Boolean =
  if (i >= j) true
  else {
    val c = s.charAt(i)
    if (c.isLetter || c.isDigit) {
      val d = s.charAt(j - 1)
      if (!(d.isLetter || d.isDigit)) isPalindrome(s, i, j - 1)
      else if (c == d) isPalindrome(s, i + 1, j - 1)
      else false
    } else isPalindrome(s, i + 1, j)
  }