BackspaceStringCompare.scala

BackspaceStringCompare.scala

object Solution {
    def backspaceCompare(left: String, right: String): Boolean = {
        sealed trait Character {}
        case object Nothing extends Character
        case object Backspace extends Character
        case object SkippedLetter extends Character
        case class FinalLetter(c: Char) extends Character
        
        case class State(string: String, pointer: Int, backspaces: Int) {
            def charOption: Option[Char] = {
                if (pointer < 0 || pointer >= string.length) {
                    None
                } else {
                    Some(string.charAt(pointer))
                }
            }
            
            def current: Character = {
                charOption match {
                    case None => Nothing
                    case Some('#') => Backspace
                    case Some(c) if backspaces == 0 => FinalLetter(c)
                    case _ => SkippedLetter
                }
            }
            
            def next: State = {
                current match {
                    case Nothing => State(string, pointer, backspaces)
                    case Backspace => State(string, pointer - 1, backspaces + 1)
                    case SkippedLetter => State(string, pointer - 1, backspaces - 1)
                    case FinalLetter(_) => State(string, pointer - 1, 0)
                }
            }
        }

        def helper(left: State, right: State): Boolean = {
            (left.current, right.current) match {
                // Reached the beginning of both strings
                case (Nothing, Nothing) => true
                // One string finished, but the other didn't -- should be no more
                // final letters in the other string
                case (FinalLetter(_), Nothing) => false
                case (_, Nothing) => helper(left.next, right)
                case (Nothing, FinalLetter(_)) => false
                case (Nothing, _) => helper(left, right.next)
                // Two final letters, compare and recurse
                case (FinalLetter(l), FinalLetter(r)) => l == r && helper(left.next, right.next)
                // Keep moving one pointer until we find two final letters
                case (FinalLetter(l), _) => helper(left, right.next)
                case (_, FinalLetter(r)) => helper(left.next, right)
                // Skips or backspaces, move both pointers
                case (_, _) => helper(left.next, right.next)
            }
        }
        helper(State(left, left.length - 1, 0), State(right, right.length - 1, 0))
    }
}