[LeetCode]Ambiguous Coordinates

这道题就是枚举，每一次分成左右两边然后每一边求加上小数点后的所有可能，然后组合起来即可。注意有的小数是不合法的：

• 字符串以0结尾，那么我们是没有办法在任何地方加小数点的。因为我们永远可以删掉末尾的0使其变得更短
• 如果以0开头，在不以0为结尾的情况下，我们只能组成0.xxx形式
• 否则枚举每一个可能形成小数点的位置

枚举左右两边O(n)，枚举小数点并且把左右的结果merge起来O(n^2)，总的时间复杂度O(n^3)。代码如下：

	class Solution {
	public:
	vector<string> ambiguousCoordinates(string S) {
	int len = S.size();
	vector<string> res;
	for (int i = 1; i < len - 2; ++i)
	{
	auto left = getValidNums(S.substr(1, i));
	auto right = getValidNums(S.substr(i + 1, len - 2 - i));
	for (const auto& lhs : left)
	for (const auto& rhs : right)
	res.push_back("(" + lhs + ", " + rhs + ")");
	}
	return res;
	}
	private:
	vector<string> getValidNums(string s)
	{
	vector<string> res;
	res.push_back(s);
	int len = s.size();
	if (len == 1)return{ s };
	if (s[0] == '0')
	{
	if (s[len - 1] == '0')return{};
	return{ "0." + s.substr(1) };
	}
	if (s[len - 1] == '0')return{ s };
	for (int i = 1; i < len; ++i)res.push_back(s.substr(0, i) + "." + s.substr(i));
	return res;
	}
	};

view raw Ambiguous Coordinates.cpp hosted with ❤ by GitHub