Clear logic backtracking C++ solution


  • 1
    P
    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> ips;
            if (s.size() == 0 || s.size() > 12)
                return ips;
            vector<string> ip;
            ipHelper(s, ips, ip, 0);
            return ips;
        }
        
        void ipHelper(string s, vector<string>& ips, vector<string> ip, int pos) {
            if (pos == s.size() && ip.size() == 4) {
                string validIp = "";
                for (int i = 0; i < 4; i++) {
                    validIp = validIp + ip[i] + ".";
                }
                validIp.pop_back();
                ips.push_back(validIp);
                return;
            }
            
            string curIp;
            for (int i = pos; i < s.size() && i < pos + 3; i++) {
                curIp.push_back(s[i]);
                if (!isValid(curIp))
                    continue;
                ip.push_back(curIp);
                ipHelper(s, ips, ip, i + 1);
                ip.pop_back();
            }
        }
        
        bool isValid(string s) {
            if (s.size() == 0 || s.size() > 3)
                return false;
            if (s.size() > 1 && s[0] == '0')
                return false;
            if (stoi(s) > 255)
                return false;
            return true;
        }
    };

Log in to reply
 

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