leetcode93 IP 주소 복원(반복 + 소거)

숫자만 포함하는 문자열을 지정하여 복원하고 가능한 모든 IP 주소 형식을 되돌려줍니다.
유효한 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

좋은 웹페이지 즐겨찾기