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
See Question&Answers more detail:os