leetcode-go/oj/pdd-2019/no4/Main.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        scanner.close();
        int lb = 0;
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        for (char c : ch1) {
            lb += c == '(' ? 1 : -1;
        }
        for (char c : ch2) {
            lb += c == '(' ? 1 : -1;
        }
        if (lb != 0) {
            System.out.println(0);
            return;
        }
        HashMap<List<Integer>, Integer> map = new HashMap<>();
        int res = dfs(ch1, ch2, 0, 0, 0, map);
        System.out.println(res);
    }

    private static int dfs(char[] ch1, char[] ch2, int i1, int i2, int lb, HashMap<List<Integer>, Integer> map) {
        if (i1 == ch1.length && i2 == ch2.length) {
            if (lb == 0) return 1;
            return 0;
        }
        Integer res;
        List<Integer> key = new ArrayList<>();
        key.add(i1);
        key.add(i2);
        key.add(lb);
        if ((res = map.get(key)) != null) return res;
        res = 0;
        if (i1 < ch1.length) {
            if (ch1[i1] == '(') {
                res = (res + dfs(ch1, ch2, i1+1, i2, lb+1, map)) % MOD;
            } else if (lb != 0) {
                res = (res + dfs(ch1, ch2, i1+1, i2, lb-1, map)) % MOD;
            }
        }
        if (i2 < ch2.length) {
            if (ch2[i2] == '(') {
                res = (res + dfs(ch1, ch2, i1, i2+1, lb+1, map)) % MOD;
            } else if (lb != 0) {
                res = (res + dfs(ch1, ch2, i1, i2+1, lb-1, map)) % MOD;
            } 
        }
        map.put(key, res);
        return res;
    }
}