leetcode 816. Ambiguous Coordinates 模糊坐标

Problem: 816. Ambiguous Coordinates 模糊坐标

解题过程

不需要用到回溯，规则是固定的，所以只需要考虑放置’,‘的地方就行，划分以后再单独放置’.‘，分两种情况考虑的，s[0]'0’或者不等于的，s[0]‘0’只能在非零数字后面放’,‘以及第一个0，s[0]!=‘0’则都可以放’,’，特殊情况是t2都是0，以及字符串最后一个字符是’0’此时不能加’.’

Code

class Solution { public: vector<string> add_decimal(string t) { if(t.size() == 1) return {t}; if(t[0]=='0') { if(t.back()=='0') return {}; t.insert(t.begin() + 1, '.'); return {t}; } if(t.back() == '0') return {t}; string tmp = t; vector<string> ret = {t}; for(int i = 1; i < tmp.size(); i++) { t = tmp; t.insert(t.begin() + i, '.'); ret.push_back(t); } return ret; } vector<string> ambiguousCoordinates(string s) { string t1, t2; vector<string> tr, p1, p2; s.erase(s.begin()); s.pop_back(); if(s[0] == '0') { for(int i = 0; i < s.size() - 1; i++) { if( (i > 0 && s[i] != '0') || (i==0)) { t1 = s.substr(0, i+1); p2 = add_decimal(t1); t2 = s.substr(i+1); if(t2.size() > 1 && t2[0]=='0') { if(stoi(t2)==0) continue; } p1 = add_decimal(t2); for(int k = 0; k < p2.size(); k++) { for(int j = 0; j < p1.size(); j++) { tr.push_back( "(" + p2[k] + ", " + p1[j] + ")" ); } } } } } else { for(int i = 0; i < s.size() - 1; i++) { t1 = s.substr(0, i+1); p2 = add_decimal(t1); t2 = s.substr(i+1); if(t2.size() > 1 && t2[0]=='0') { if(stoi(t2)==0) continue; } p1 = add_decimal(t2); for(int k = 0; k < p2.size(); k++) { for(int j = 0; j < p1.size(); j++) { tr.push_back( "(" + p2[k] + ", " + p1[j] + ")" ); } } } } return tr; } };