Thursday, September 5, 2013

Day 43, #93 Restore IP Addresses

Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
----------------------------------------------------
DFS

class Solution {
public:
    int stringToInt (string s) {
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            num = num * 10;
            int temp  = s[i] - '0';
            num = num + temp;
        }
        return num;
    }

    void rec (string cur, string s, int count, vector<string> &ret) {
        if (s.length() == 0 && count == 4) {
            ret.push_back(cur);
        }else if (count < 4 && s.length() != 0) {
            if (count != 0) { // no '.' before the first part 
                cur = cur + ".";
            }
            string temp;
            if (s.length() >= 1) {
                temp = cur + s[0];
            rec(temp,s.substr(1),count+1,ret);
            }
            if (s.length() >= 2 && s[0] != '0') {
                temp = cur + s.substr(0,2);
            rec(temp,s.substr(2),count+1,ret);
            }
            if (s.length() >= 3 && s[0] != '0') {
                temp = cur + s.substr(0,3);
                if (stringToInt(s.substr(0,3)) < 256) {
                    rec(temp,s.substr(3),count+1,ret);
                }
            }
        }
        
    }

    vector<string> restoreIpAddresses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> ret;
        rec("",s,0,ret);
        return ret;
        
    }
};
Update on Sep-21-2014 
Same algorithm but with index
class Solution {
public:
    void rec(vector<string> &rt, string s, int index, int count,string ip) {
        if (count == 4 && index == s.length()) {
            rt.push_back(ip);
            return;
        }
        
        if (count > 4 || index > s.length()) return;
        
        if (count != 0) {
            ip += "."; 
        }
        
        rec(rt,s,index + 1, count + 1, ip + s.substr(index,1));
        
        if (index + 1 < s.length() && s[index] != '0') {
            string sub = s.substr(index,2);
            rec(rt,s,index + 2, count + 1, ip + sub);
        }
        
        if (index + 2 < s.length() && s[index] != '0') {
            string sub = s.substr(index,3);
            if (stoi(sub) < 256) {
                rec(rt,s,index + 3, count + 1, ip + sub);
            }
        }
        
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> rt;
        if (s == "") return rt;
        rec(rt,s,0,0,"");
        
        return rt;
    }
};

No comments:

Post a Comment