Time and space complexity using Tail recursion

Question

Can anyone please help me to understand the time and space complexity of algo to balance parenthesis

def isValid(s: String): Boolean = {
@annotation.tailrec
def go(i: Int, stack: List[Char]): Boolean = {
  if (i >= s.length) {
    stack.isEmpty
  } else {
    s.charAt(i) match {
      case c @ ('(' | '[' | '{')                     => go(i + 1, c +: stack)
      case ')' if stack.isEmpty || stack.head != '(' => false
      case ']' if stack.isEmpty || stack.head != '[' => false
      case '}' if stack.isEmpty || stack.head != '{' => false
      case _                                         => go(i + 1, stack.tail)
    }
  }
}
go(0, Nil)

}

As per my undertanding, tail recursion reduces space to 0(1) complexity but here I am using additional data structure of List as accumulator, can anyone please explain how the space complexity and time complexity can be calculated

Answer 1

There is a bug in your code: you are pushing only parentheses on stack, but pop everything, so this implementation only works for strings that only contain parentheses ... not sure if that was the intent. With the proper implementation, it should be liner in time, and the space complexity would be linear too, but not on the length of the entire string, only on the number of parentheses it contains.

    val oc = "([{" zip ")]}"
    object Open {  def unapply(c: Char) = oc.collectFirst { case (`c`, r) => r }}
    object Close { def unapply(c: Char) = oc.collectFirst { case (_, `c`) => c }}
    object ## { def unapply(s: String) = s.headOption.map { _ -> s.tail }}


    def go(s: String, stack: List[Char] = Nil): Boolean = (s, stack) match {
       case ("", Nil) => true
       case ("", _) => false
       case (Open(r) ## tail, st) => go(tail, r :: st)
       case (Close(r) ## tail, c :: st) if c == r => go(tail, st)
       case (Close(_) ## _, _) => false
       case (_ ## tail, st) => go(tail, st)
     }
    
     go(s)

(to be fair, this is actually linear in space because of s.toList :) The esthete inside me couldn't resist. You can turn it back to s.charAt(i) if you'd like, it just wouldn't look as pretty anymore ... or use s.head and `s.