WHO CAN BEAT THIS CODE ?


  • 72
    M
        // c++  code
        vector<string> restoreIpAddresses(string s) {
            vector<string> ret;
            string ans;
            
            for (int a=1; a<=3; a++)
            for (int b=1; b<=3; b++)
            for (int c=1; c<=3; c++)
            for (int d=1; d<=3; d++)
                if (a+b+c+d == s.length()) {
                    int A = stoi(s.substr(0, a));
                    int B = stoi(s.substr(a, b));
                    int C = stoi(s.substr(a+b, c));
                    int D = stoi(s.substr(a+b+c, d));
                    if (A<=255 && B<=255 && C<=255 && D<=255)
                        if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
                            ret.push_back(ans);
                }    
            
            return ret;
        }

  • 2
    H

    you don't need the fourth for loop with d. since d = len - (a+b+c) and

    //java int D= Integer.valueof(s.substr(a+b+c)))

  • 0
    T

    very smart solution! I like it.


  • 0
    G

    @mitbbs8080
    I like your post title!


  • 0
    J
    This post is deleted!

  • 0
    L

    No one can beat this code!


  • 7
    O

    thanks for sharing, my java solution based your idea

    public List<String> restoreIpAddresses(String s) {
    		List<String> ret = new ArrayList<>();
    		
    		StringBuffer ip = new StringBuffer();
    		for(int a = 1 ; a < 4 ; ++ a)
    		for(int b = 1 ; b < 4 ; ++ b)
    	        for(int c = 1 ; c < 4 ; ++ c)
    		for(int d = 1 ; d < 4 ; ++ d)
    		{
    			if(a + b + c + d == s.length() )
    			{
    				int n1 = Integer.parseInt(s.substring(0, a));
    				int n2 = Integer.parseInt(s.substring(a, a+b));
    				int n3 = Integer.parseInt(s.substring(a+b, a+b+c));
    				int n4 = Integer.parseInt(s.substring(a+b+c));
    				if(n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255)
    				{
    					ip.append(n1).append('.').append(n2)
    						.append('.').append(n3).append('.').append(n4);
    					if(ip.length() == s.length() + 3) ret.add(ip.toString());
    					ip.delete(0, ip.length());
    				}
    			}
    		}
    		return ret;
        }
    

  • 0
    W

    @mitbbs8080 Slight refactor based on your smart solution :)

    vector<string> restoreIpAddresses(const string &s) {
        vector<string> res;
        for (auto a = 1; a < 4; ++a)
        for (auto b = 1; b < 4; ++b)
        for (auto c = 1; c < 4; ++c)
        for (auto d = 1; d < 4; ++d)
            if (a + b + c + d == s.size()) {
                auto A = stoi(s.substr(0, a));
                auto B = stoi(s.substr(a, b));
                auto C = stoi(s.substr(a + b, c));
                auto D = stoi(s.substr(a + b + c));
                if (A > 255 || B > 255 || C > 255 || D > 255) continue;
                auto ip = to_string(A) + '.' + to_string(B) + '.' + to_string(C) + '.' + to_string(D);
                if (ip.size() == s.size() + 3) res.push_back(ip);
            }
        return res;
    }
    

  • 3
    S

    Smart solution!! my java solution based on your ideas, without 'd' loop.

    public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<String>();
            int len = s.length();
            StringBuffer ip = new StringBuffer();
             for (int a=1; a<=3; a++){
                 for (int b=1; b<=3; b++){
                     for (int c=1; c<=3; c++){
                         int d = len - a - b - c;
                         if ( d > 0 && d <= 3 && a+b+c+d == s.length()) {
                             int A = Integer.parseInt(s.substring(0, a));
                             int B = Integer.parseInt(s.substring(a, a+b));
                             int C = Integer.parseInt(s.substring(a+b, a+b+c));
                             int D = Integer.parseInt(s.substring(a+b+c));
                             if (A<=255 && B<=255 && C<=255 && D<=255){
                                 ip.append(A).append(".").append(B).append(".").append(C).append(".").append(D);
                                 if( ip.length() == len + 3){
                                     res.add(ip.toString());
                                 }
                                 ip = new StringBuffer();
                             }
                         }   
                     }
                 }
             }
            return res;
        }
    

  • 2
    C

    @superlee828 do you consider the corner case like 0 is the leading number?


  • 2
    D

    You can improve performance in quite a few ways:

    1. If length of string is 12, you don't need all those loops and length of A B C D all will be 3 always. Similarly if length of string is 10 then for case when you consider length of A as 1 then length B,C,D will be always 3.
    2. Instead of calculating A,B,C,D all at once, calculate one and check one, this will be better for performance. like in case string is "25525511222" here according to code 1st value of A will be "2" and B will be "552" which is invalid you don't need rest of calculations in this case.

  • 0
    E

    @Chaofb I think this line "ip.length() == len + 3" is for checking the leading 0's


  • 0
    P

    @ethancoding said in WHO CAN BEAT THIS CODE ?:

    .

    I think so either.


  • 0
    W

    Excellent solution!I like it very much!


  • -1
    This post is deleted!

  • 0
    S

    wonderful...kind of feeling that 独孤求败 had experienced.


  • 0
    L

    damn so smart solution!


  • 0
    M

    @Chaofb
    if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
    Well this line of code is enough.


  • 0
    M

    Excellent idea!
    However your code runs 3ms, while my dumb code runs 0ms...

    bool test(string tester){
        if(tester.size()<1||tester.size()>3)return false;
        if(tester.size()>1&&tester[0]=='0')return false;
        if(tester.size()==3&&tester[0]>'2')return false;
        if(tester.size()==3&&tester[0]=='2'&&(tester[1]-'0')*10+tester[2]-'0'>55)return false;
        return true;
    }
    class Solution {
    public:   
        void getans(vector<string>& ans,string s,string temp,int n,int begin){
            string tester;
            if(n)temp+='.';
            if(n==3){
                for(int i=begin;i<s.length();i++)tester+=s[i];
                if(test(tester)){
                    temp+=tester;
                    ans.push_back(temp);
                }
                return;
            }
            for(int i=0;i<3;i++){
                if(begin+i>=s.size())break;
                tester+=s[begin+i];
                temp+=s[begin+i];
                if(test(tester))getans(ans,s,temp,n+1,begin+i+1);
            }
        }
        vector<string> restoreIpAddresses(string s) {
            vector<string>ans;
            if(s.size()<4||s.size()>12)return ans;
            getans(ans,s,"",0,0);
            return ans;
        }
    };
    

    emmm....
    Forgive me for being a bit messy


Log in to reply
 

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