leetcode-go/oj/pdd-2019/no4/exp.go

package main

import "fmt"

const MOD int = 1000000007

func main() {
	var s1, s2 string
	fmt.Scanln(&s1)
	fmt.Scanln(&s2)
	lb := 0
	for _, r := range s1 {
		if r == '(' {
			lb++
		} else {
			lb--
		}
	}
	for _, r := range s2 {
		if r == '(' {
			lb++
		} else {
			lb--
		}
	}
	if lb != 0 {
		fmt.Println(0)
		return
	}
	m := make(map[[3]int]int)
	res := dfs([]rune(s1), []rune(s2), len(s1), len(s2), 0, 0, 0, m)
	fmt.Println(res)
}

func dfs(s1, s2 []rune, l1, l2, i1, i2, lb int, m map[[3]int]int) int {
	if i1 == l1 && i2 == l2 {
		if lb == 0 {
			return 1
		}
		return 0
	}
	if v, ok := m[[3]int{i1, i2, lb}]; ok {
		return v
	}
	res := 0
	if i1 < l1 {
		if s1[i1] == '(' {
			res = (res + dfs(s1, s2, l1, l2, i1+1, i2, lb+1, m)) % MOD
		} else if lb != 0 {
			res = (res + dfs(s1, s2, l1, l2, i1+1, i2, lb-1, m)) % MOD
		}
	}
	if i2 < l2 {
		if s2[i2] == '(' {
			res = (res + dfs(s1, s2, l1, l2, i1, i2+1, lb+1, m)) % MOD
		} else if lb != 0 {
			res = (res + dfs(s1, s2, l1, l2, i1, i2+1, lb-1, m)) % MOD
		}
	}
	m[[3]int{i1, i2, lb}] = res
	return res
}