Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def solve(s: String): Int = {
- val solutions = Array.ofDim[Int](s.length() + 1, s.length() + 1)
- solutions(0)(0) = 1
- (0 to s.length() - 1).foreach { subproblem =>
- (0 to s.length()).foreach { openParens =>
- val currentCount = solutions(subproblem)(openParens)
- s(subproblem) match {
- case '(' => if (openParens < s.length()) solutions(subproblem + 1)(openParens + 1) += currentCount
- case ')' => if (openParens > 0) solutions(subproblem + 1)(openParens - 1) += currentCount
- case '*' => {
- if (openParens < s.length()) solutions(subproblem + 1)(openParens + 1) += currentCount
- solutions(subproblem + 1)(openParens) += currentCount
- if (openParens > 0) solutions(subproblem + 1)(openParens - 1) += currentCount
- }
- }
- }
- }
- return solutions(s.length())(0)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement