Leetcode第816题：模糊坐标（Ambigious cooridinates）

解题思路

题目给出字符串s为某些原始坐标字符串去掉所有逗号，小数点和空格后得到的字符串，其中需要满足原始坐标表示中的数不会存在多余的零。
现在我们要求出所有能生成字符串s的所有可能的原始字符串。 我们可以尝试将原始坐标字符串中去掉的逗号，小数点和空格进行还原——首先在字符串s中枚举添加逗号和空格的位置，将s的数字部分为两个部分，前一部分为原始坐标x坐标去掉（若存在）小数点后的数字，后一部分为原始坐标y坐标去掉（若存在）小数点后的数字。然后我们分别对于前后部分数字枚举添加小数点的位置（也可以不添加），其中添加或者不添加小数点合法情况需要满足的条件：

• 不添加小数点和添小数点后的整数部分都需要满足当前表示数字为0或者为不含前导零的正数。
• 添加小数点后，小数部分需要满足其末尾不为0。

然后对于前后部分的合法方案进行一一匹配得到此时情况的合法原始坐标字符串。
来源：题解

代码如下：

class Solution {
public:
    vector<string> getPos(string s) {
        vector<string> pos;
        if (s[0] != '0' || s == "0")
            pos.push_back(s);
        for (int p = 1; p < s.size(); ++p) {
            if ((p != 1 && s[0] == '0') || s.back() == '0') 
                continue;
            pos.push_back(s.substr(0, p) + "." + s.substr(p));
        }
        return pos;
    }
    vector<string> ambiguousCoordinates(string s) {
        int n = s.size() - 2;
        vector<string> res;
        s = s.substr(1, s.size() - 2);
        for (int l = 1; l < n; ++l) {
            vector<string> lt = getPos(s.substr(0, l));
            if (lt.empty()) continue;
            vector<string> rt = getPos(s.substr(l));
            if (rt.empty()) continue;
            for (auto& i : lt) {
                for (auto& j : rt) {
                    res.push_back("(" + i + ", " + j + ")");
                }
            }
        }
        return res;
    }
};

原文地址：http://www.cnblogs.com/hql5/p/16866440.html