LC 93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: “25525511135” Output: [“255.255.11.135”, “255.255.111.35”]

An IP address has 4 parts. Each part will have a valid number in [0,255] Since each group can have 1, 2 or 3 numbers, we have 3x3x3x3 ways to splice the number.

BF

Just all 81 ways to splice the number and output all possible combination.

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        //use 4 nested for loop to generate all possible way 
        //to slice
        vector<string> res;
        for(int i = 1; i <= 3; i ++){
            for(int j = 1; j <= 3; j ++){
                for(int k = 1; k <= 3; k ++){
                    for(int l = 1; l <= 3; l ++){
                        if(i + j + k + l != s.size())
                            continue;
                        int i1 = stoi(s.substr(0, i));
                        int i2 = stoi(s.substr(i, j));
                        int i3 = stoi(s.substr(i + j, k));
                        int i4 = stoi(s.substr(i + j + k, l));
                        //cout<<i1 << " " << i2 <<" "<< i3<<" " << i4<< '\n';
                        if(i1 <= 255 && i2 <= 255 && i3 <= 255 && i4 <=255){
                            string ans = to_string(i1) + "." + to_string(i2) + "." + to_string(i3) + "." + to_string(i4);
                            //cout<<"ans is "<< ans<<endl;
                            if(ans.size() == s.size() + 3){
                                res.push_back(ans);
                                //cout<<ans<<endl;
                            }

                        }
                    }
                }
            }
        }//end of most outer forloop
        return res;
    }

};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax