def solveSudoku(self, board):
        m = len(board)
        n = len(board) if m else 0
        seen, points =set(), []
        for i in range(m):
            for j in range(n):
                if board[i][j] == '.':
                    points.append((i, j))
                else:
                    seen.update([str(i) + 'r' + board[i][j], str(j) + 'c' + board[i][j], str(i/3) + str(j/3) + board[i][j]])
        def dfs(points, i, board, v):
            if i == len(points): return True
            x, y = points[i]
            for j in range(1, 10):
                tmp = set([str(x) + 'r' + str(j), str(y)+ 'c'+ str(j), str(x/3) + str(y/3) + str(j)])
                if not tmp&v:
                    board[x][y] = str(j)
                    if dfs(points, i + 1, board, v | tmp ): return True
                    board[x][y] = '.'
            return False
        dfs(points, 0, board, seen)

let dp[i] is the number of longest valid Parentheses ended with the i - 1 position of s, then we have the following relationship:
dp[i + 1] = dp[p] + i - p + 1 where p is the position of '(' which can matches current ')' in the stack.

  def longestValidParentheses(self, s):
    dp, stack = [0]*(len(s) + 1), []
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            if stack:
                p = stack.pop()
                dp[i + 1] = dp[p] + i - p + 1
    return max(dp)