leetcode93 IP 주소 복원(반복 + 소거)
1524 단어 알고리즘 데이터 구조
유효한 IP 주소는 딱 네 개의 정수(각 정수는 0에서 255 사이로 구성), 정수 사이는'.'갈라놓다
예:
입력: 25525511135 출력: ["255.255.11.135", "255.255.111.35"]
사고방식:귀속+거슬러 올라가기
우선 귀속된 네 가지 인자(원 문자열s, 현재 ip의cur를 저장하고 모든 가능한 ip집합ans, 현재 위치pos)의 귀속 출구를 확정한다. cur에 네 개의 숫자가 있는데 그것이 바로 현재 ip의 네 부분을 포함하고pos=s.length()이다. 그리고 이때 ip의 점분 10진법 형식으로 ans수조에 넣어야 한다.귀속체: ip의 각 부분에 최대 3개의 숫자가 있다. 현재 위치에서 1개의 숫자, 2개의 숫자, 3개의 숫자 세 가지 상황을 선택하면 현재 ip의 일부가cur에 들어가고 다음 층으로 귀속되는 것을 확정한다.이 층이 귀속되어 나오면 거슬러 올라가려면 그 전에 넣고 삭제해야 한다.255보다 크고 선도 0이 있는 특수한 상황을 주의해야 한다.그리고 수조가 경계를 넘지 않도록 주의해야 한다.
AC 코드:
class Solution {
public:
vector restoreIpAddresses(string s) {
vector ans;
if(s.length()<4) return ans;
vector cur;
dfs(s,cur,ans,0);
return ans;
}
void dfs(string s,vector& cur,vector& ans,int pos){
if(cur.size()==4){
if(pos==s.length()){
string ip="";
for(int i=0;i<4;i++){
ip += ((i==3)?cur[i]:cur[i]+".");
}
ans.push_back(ip);
}
return;
}
string net ="";
for(int i=0;i<3;i++){
if(net=="0") break;
if(pos+i