BackspaceStringCompare.scala

BackspaceStringCompare.scala

object Solution {
    def backspaceCompare(left: String, right: String): Boolean = {
        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 finalLetter: Option[Char] = {
                charOption match {
                    case Some('#') => None
                    case Some(_) if backspaces == 0 => charOption
                    case _ => None
                }
            }
            
            def next: State = {
                charOption match {
                    case Some('#') => State(string, pointer - 1, backspaces + 1)
                    case Some(_) => State(string, pointer - 1, Math.max(backspaces - 1, 0))
                    case None => State(string, pointer, backspaces)
                }
            }
        }

        def helper(left: State, right: State): Boolean = {
            (left.charOption, right.charOption) match {
                // Reached beginning of both strings
                case (None, None) => true
                // Reached beginning of one string, but not the other. There should
                // be no more final letters in the other one
                case (Some(_), None) => left.finalLetter.isEmpty && helper(left.next, right)
                case (None, Some(_)) => right.finalLetter.isEmpty && helper(left, right.next)
                case (Some(_), Some(_)) => {
                    (left.finalLetter, right.finalLetter) match {
                        case (None, None) => helper(left.next, right.next)
                        case (Some(_), None) => helper(left, right.next)
                        case (None, Some(_)) => helper(left.next, right)
                        // Two final letters -- they should match
                        case (Some(l), Some(r)) => l == r && helper(left.next, right.next)
                    }
                }
                
            }
        }
        helper(State(left, left.length - 1, 0), State(right, right.length - 1, 0))
    }
}