笛卡尔乘积问题

笛卡尔乘积问题的判别

笛卡尔问题的一个特点是有很多个种类的子结果的拼接。目前遇到的只是字符串的拼接。

通用解决思路

• 分步求解结果，最后拼接；

例题

Leetcode 816.模糊坐标

class Solution {
public:
vector<string> addSymbol(string s) {
vector<string> res;
int length = s.length();
for(int i = 1; i <= length - 1; i++) {
string temp = s;
//
剪枝
if(temp[0] == '0' && i > 1) continue;
if(temp[length-1] == '0') continue;
temp.insert(i, ".");
res.push_back(temp);
}
if(s == "0" || s[0] != '0') res.push_back(s);
return res;
}
vector<string> ambiguousCoordinates(string S) {
//
S去除两边的括号
string s = S.substr(1, S.size()-2);
int length = s.length();
//
结果保存
vector<string> res;
//
遍历逗号插入位置
for(int i = 1; i <= length - 1; i++) {
//
分割字符串
vector<string> x = addSymbol(s.substr(0,i));
vector<string> y = addSymbol(s.substr(i, length-i));
//
笛卡尔乘积
for(auto i : x) {
for(auto j : y) {
string temp = "(" + i + ", " + j + ")";
res.push_back(temp);
}
}
}
return res;
}
};

最后

以上就是还单身黑裤为你收集整理的笛卡尔乘积问题的全部内容，希望文章能够帮你解决笛卡尔乘积问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。