My c++ answer 5 ms o(n^3)


  • 0
    M

    class Solution {
    public:
    vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    if(s=="")
    return res;
    string str1,str2,str3,str4,ans;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    for(int k=1;k<=3&&i+j+k<s.length();k++)
    {
    str1=s.substr(0,i);
    str2=s.substr(i,j);
    str3=s.substr(i+j,k);
    str4=s.substr(i+j+k);
    if(judge(str1)&&judge(str2)&&judge(str3)&&judge(str4))
    {
    ans=str1+"."+str2+"."+str3+"."+str4;
    res.push_back(ans);
    }
    }
    vector<string>::iterator iter=unique(res.begin(),res.end());
    res.erase(iter,res.end());
    return res;
    }
    bool judge(string &s) {
    if(s[0]=='0'&&s.length()>1)
    return false;
    else
    {
    int k = atoi(s.c_str());
    if((0<k && k < 256)||(0==k&&1==s.length()))
    return true;
    else return false;
    }
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.