leetcode第93題:IPアドレスの復元(C++)
3822 ワード
93.IPアドレス-バックルを復元する(LeetCode)
最初の考え方は文字列を3回切断し、左から1枚ずつ(最大3桁)切ることです.
では、3つのカットポイント(下付き)i,j,kがあります.
n = s . s i z e ( ) n = s.size() n=s.size()
0 = < i < j < k < n − 1 0 =< i < j < k < n-1 0=これらは文字列sを4つの部分に分けている:[0,i],[i+1,j],[j+1,k],[k+1,n−1][0,i],[i+1,j],[j+1,k],[k+1,n−1][0,i],[j+1,k],[k+1,n−1,[k],[k+1,n−1]
4つの部分の文字列が変換された数字は、区間[0255]の間にあるはずです.したがって、数字は最大3桁、つまり2つのカットポイントの間に最大3文字しかありません.
0 < = i < = 2 0 <= i <= 2 0<=i<=2 j − i < = 3 j - i <= 3 j−i<=3 k − j < = 3 k - j <= 3 k−j<=3 n − 1 − k < = 3 n-1 - k <= 3 n−1−k<=3
我々の目的は、上記の制約に従って適切な切断点を探せばよいので、自然と、切断が2桁の場合、現在の要求に合致するに違いないが、3桁を切断する場合、255より大きいかどうかを判断する必要があり、それより大きい場合、このような切断方式は通用しない.
詳細については、0は単独としてのみ使用でき、00.00は発生しません.
暴力解法は簡単そうに見えるが、実は考えなければならない細部が多い.
書き方を変えて、遡りましょう.実は遡りは本質的に列挙であり、剪定は制約条件を加えるので、暴力法と性能が悪いはずです.
最初の考え方は文字列を3回切断し、左から1枚ずつ(最大3桁)切ることです.
では、3つのカットポイント(下付き)i,j,kがあります.
n = s . s i z e ( ) n = s.size() n=s.size()
0 = < i < j < k < n − 1 0 =< i < j < k < n-1 0=
4つの部分の文字列が変換された数字は、区間[0255]の間にあるはずです.したがって、数字は最大3桁、つまり2つのカットポイントの間に最大3文字しかありません.
0 < = i < = 2 0 <= i <= 2 0<=i<=2 j − i < = 3 j - i <= 3 j−i<=3 k − j < = 3 k - j <= 3 k−j<=3 n − 1 − k < = 3 n-1 - k <= 3 n−1−k<=3
我々の目的は、上記の制約に従って適切な切断点を探せばよいので、自然と、切断が2桁の場合、現在の要求に合致するに違いないが、3桁を切断する場合、255より大きいかどうかを判断する必要があり、それより大きい場合、このような切断方式は通用しない.
詳細については、0は単独としてのみ使用でき、00.00は発生しません.
暴力解法は簡単そうに見えるが、実は考えなければならない細部が多い.
class Solution {
public:
vector restoreIpAddresses(string s) {
int n = s.size();
if(n > 12 || n < 4) return vector();
vector res;
string ans;
for(int i = 1; i <= 3; ++i){
if(n - i < 3 || n - i > 9) continue; //
string s1 = s.substr(0, i);
if(i== 3 && stoi(s1) > 255) continue;
string// 0 （ ）
if(i == 2 && s1[0] == '0' || i == 3 && s1[0] == '0') continue; //0
for(int j = 1; j <= 3; ++j){
if(n-i-j < 2 || n-i-j > 6) continue;
string s2 = s.substr(i, j);
if(j == 3 && stoi(s2) > 255) continue;
if(j == 2 && s2[0] == '0' || j == 3 && s2[0] == '0') continue;
for(int k = 1; k <= 3; ++k){
if(n-i-j-k < 1 || n-i-j-k > 3) continue;
string s3 = s.substr(i+j, k);
if(k == 3 && stoi(s3) > 255) continue;
if(k == 2 && s3[0] == '0' || k == 3 && s3[0] == '0') continue;
string s4 = s.substr(i+j+k, n-i-j-k);
if(stoi(s4) > 255) continue;
if(n-i-j-k == 2 && s4[0] == '0' || n-i-j-k == 3 && s4[0] == '0') continue;
res.push_back(s1+"." + s2 + "." + s3 + "." + s4);
}
}
}
return res;
}
};
書き方を変えて、遡りましょう.実は遡りは本質的に列挙であり、剪定は制約条件を加えるので、暴力法と性能が悪いはずです.
class Solution {
public:
vector res;
bool isOk(int num, int beg, int i, string &s){ // beg i
string str = s.substr(beg, i);
if(s.size() - beg- i < 3 - num || s.size() - i - beg > 3*(3 - num)) return false; //
if(i == 3 && stoi(str) > 255) return false; //i 0 1 255
if((i == 2 && str[0] == '0') || (i == 3 && str[0] == '0')) return false; // 0
return true;
}
void backtrack(int num, int beg, string str, string &s){// num ( 3 ) ，beg
if(num == 3){
if(isOk(num, beg, s.size()-beg, s)) // s
res.push_back(str+s.substr(beg, s.size()-beg));
return;
}
for(int i = 1; i <= 3; ++i){ // beg ， 1/2/3
if(isOk(num, beg, i, s)) //
backtrack(num+1, beg+i, str+s.substr(beg, i)+".", s); // （ ）
}
return;
}
vector restoreIpAddresses(string s) {
backtrack(0, 0, "", s);
return res;
}
};