leetcode 93. Restore IP Addresses（DFS，模拟）

题目链接

题意

给定一段序列，判断可能组成ip数的所有可能集合

思路

可以采用模拟或者DFS的想法，把总的ip数分成四段，每段判断是否满足题意

class Solution {

public:

    vector<string> ans;

    vector<string> restoreIpAddresses(string s){

        if(!s.size()) return ans;

        solve(0,0,s,"");

        return ans;

    }

    //方法二: dfs

    void solve(int p,int cnt,string &s,string tmp){

        if(cnt>=4 && p<s.size()) return ;

        if(p>=s.size()){//分成4段

            if(cnt==4){

                ans.push_back(tmp);

            }

            return ;

        }

        for(int i=1;i<=3;i++){//每段的长度最长不超过3

            if(p+i>s.size()) return;

            string t=s.substr(p,i);

            int it=stoi(t);

            if(to_string(it)!=t || it>255) continue;

            // if(!cnt) tmp+=t;

            // else tmp+="."+t;

            solve(p+i,cnt+1,s,tmp+(cnt?"."+t:t));

        }

    }

    //方法一：直接遍历所有情况

    vector<string> restoreIpAddresses(string s) {

        int n=s.size();

        if(!n)  return ans;

        for(int a=1;a<=3;a++)

            for(int b=1;b<=3;b++)

                for(int c=1;c<=3;c++){

                    int d=n-(a+b+c);

                    if(d<1 || d>3) continue;

                    string a1=s.substr(0,a);

                    string b1=s.substr(a,b);

                    string c1=s.substr(a+b,c);

                    string d1=s.substr(a+b+c);

                    if(to_string(stoi(a1))!=a1 || to_string(stoi(b1))!=b1 ||

                      to_string(stoi(c1))!=c1 || to_string(stoi(d1))!=d1) continue;

                    if(stoi(a1)>255 || stoi(b1)>255 || stoi(c1)>255 || stoi(d1)>255) continue;

                    ans.push_back(a1+"."+b1+"."+c1+"."+d1);

                    }

        return ans;

    }

};

巴特西

leetcode 93. Restore IP Addresses（DFS，模拟）

题目链接

题意

思路

最新文章

热门文章

巴特西

leetcode 93. Restore IP Addresses（DFS， 模拟）

题目链接

题意

思路

最新文章

热门文章

leetcode 93. Restore IP Addresses（DFS，模拟）