Advertisement
bytter

Untitled

Feb 6th, 2021
1,503
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 0.90 KB | None | 0 0
  1.   def solve(s: String): Int = {
  2.     val solutions = Array.ofDim[Int](s.length() + 1, s.length() + 1)
  3.     solutions(0)(0) = 1
  4.     (0 to s.length() - 1).foreach { subproblem =>
  5.       (0 to s.length()).foreach { openParens =>        
  6.         val currentCount = solutions(subproblem)(openParens)
  7.         s(subproblem) match {
  8.           case '(' => if (openParens < s.length()) solutions(subproblem + 1)(openParens + 1) += currentCount
  9.           case ')' => if (openParens > 0) solutions(subproblem + 1)(openParens - 1) += currentCount
  10.           case '*' => {
  11.             if (openParens < s.length()) solutions(subproblem + 1)(openParens + 1) += currentCount
  12.             solutions(subproblem + 1)(openParens) += currentCount
  13.             if (openParens > 0) solutions(subproblem + 1)(openParens - 1) += currentCount
  14.           }
  15.         }        
  16.       }
  17.     }
  18.    
  19.     return solutions(s.length())(0)
  20.   }
  21.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement