[LeetCode]Minimum Area Rectangle

这道题很明显是DP的题目，我们用dp[i]表示s[0:i]中所有的distinct subsequence的话(包括empty string)，我们需要得出递归公式：

• 对于dp[i]来说，如果位于i处的s[i]之前都没有出现的话，很明显dp[i] = dp[i - 1] * 2，因为所有之前的distinct subsequence都可以append s[i]而生成新的没有重复的subsequence。
• 如果s[i]之前出现过，比如s[j] == s[i]，那么s[0:j - 1]的distinct subsequence和s[i]组成的subsequence就会产生重复，所以我们要减去dp[j - 1], dp[i] = 2 * dp[i - 1] - dp[j - 1]

我们根据上面的递归公式求即可，最后结果去掉empty string即可。时间空间复杂度都为O(N)，代码如下：

	class Solution {
	public:
	int minAreaRect(vector<vector<int>>& points) {
	unordered_set<long> set;
	for (auto& point : points)
	set.insert(point[0] * 40001 + point[1]);
	int res = 0;
	for (int i = 0; i < points.size(); ++i)
	{
	for (int j = i + 1; j < points.size(); ++j)
	{
	auto point1 = points[i], point2 = points[j];
	if (point1[0] != point2[0] && point1[1] != point2[1])
	{
	if (set.find(point1[0] * 40001 + point2[1]) != set.end() && set.find(point2[0] * 40001 + point1[1]) != set.end())
	{
	int area = abs(point1[0] - point2[0]) * abs(point1[1] - point2[1]);
	res = res? min(res, area): area;
	}
	}
	}
	}
	return res;
	}
	};

view raw Minimum Area Rectangle.cpp hosted with ❤ by GitHub