scala palindrome function with forloop

Question

Would like to know the Scala equivalent of Java palindrome function, writing forloop with multiple variables is tricky in scala

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

Im able to write code in scala for palindrome but the space complexity is O(1) in above solution, and the below one has 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

What about this?

def isPalindrome(str: String): Boolean = {
  val len = str.length - 1

  @annotation.tailrec
  def loop(i: Int): Boolean = {
    val j = len - i
    if (i >= j) true
    else {
      if (str(i).toLower != str(j).toLower) false
      else loop(i + 1)
    }
  }

  loop(i = 0)
}

I omitted the pre-processing part, but you can add that if you want.

Answer 2

If you really want loops, you can do this. The space complexity is constant/O(1) because the only variables you have are i, j, a, and b. The time complexity's O(n), same as the Java version.

def isPalindrome(s: String): Boolean = {
  var i = 0
  var j = s.length - 1
  while (i < j) {
    val a = s.charAt(i)
    if (a.isLetter || a.isDigit) {
      val b = s.charAt(j)
      if (b.isLetter || b.isDigit) {
        if (a != b) return false
      }
    }
    i += 1
    j -= 1
  }
  true
}

Why not use recursion though?

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

Output for both is

false
true
true
true

for

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

Link to Scastie: https://scastie.scala-lang.org/oTetGkfsQ5OLUowTylghFw

EDIT: The recursive method without the return keyword, which can cause problems, as @Luis Miguel Mejía Suárez said:

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