Straight Forward and Simple C++ Solution(Three for loops)


  • 1
    K

    The idea is pretty simple and straight forward. Splitting the string into four parts and verifying each part. If all four parts are valid, then this is a valid IP and then push back to result. The only thing we should be careful is how to determine the position of each substring.

    class Solution {
        public:
            vector<string> restoreIpAddresses(string s) {
                vector<string> res;
                int len=s.size();
                for(int i=1;i<4&&(i-1)<len-3;i++){
                    for(int j=1;j<4&&(j+i-1)<len-2;j++){
                        for(int k=1;k<4&&(k+j+i-1)<len-1;k++){
                            string s1=s.substr(0,i);
                            string s2=s.substr(i,j);
                            string s3=s.substr(i+j,k);
                            string s4=s.substr(i+j+k,len-i-j-k);
                            if(isValid(s1)&&isValid(s2)&&isValid(s3)&&isValid(s4)){
                                string solution=s1+"."+s2+"."+s3+"."+s4;
                                res.push_back(solution);
                            }
                        }
                    }
                }
                return res;
            }
            bool isValid(string s){
                if(s.size()>3||s.size()==0||(s.front()=='0'&&s.size()>1)||stoi(s)>255) return false;
                return true;
            }
        };

  • 0
    M

    I have the similar way like you. (But JAVA)
    But in my isVaild it just a very simple check : value < 256 or not.

    Other check I can use /Below/

    String input = String.valueOf(pass[0]) + "." + String.valueOf(pass[1]) +
    "." + String.valueOf(pass[2]) + "." + String.valueOf(pass[3]);

    /Below/

    if (input.length() - 3 == s.length())
    rtn_list.add(input);

    to Finish it


  • 0
    P

    You idea is ok for this problem. But it's not backtracking, so it couldn't stop search immediately when the prefix is already wrong!


Log in to reply
 

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