Leetcode 93 Solution

This article provides solution to leetcode question 93 (restore-ip-addresses)
Categories:
Tags:
Access this page by simply typing in "lcs 93" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/restore-ip-addresses

Solution

class Solution {
    vector<string> m_res;

public:
    void restoreIpAddresses(const string& s, int i, vector<int>& ip)
    {
        if (ip.size() == 4 && i < s.size())
            return;

        if (i == s.size())
        {
            if (ip.size() == 4)
            {
                string ipstr = to_string(ip[0]) + "." + to_string(ip[1]) + "." + to_string(ip[2]) + "." + to_string(ip[3]);
                m_res.push_back(ipstr);
            }

            return;
        }

        if (s[i] == '0')
        {
            ip.push_back(0);
            restoreIpAddresses(s, i + 1, ip);
            ip.pop_back();
        }
        else
        {
            for (int j = i; j < s.size(); j++)
            {
                int val = atoi(s.substr(i, j - i + 1).c_str());

                if (val >= 256)
                    break;

                ip.push_back(val);
                restoreIpAddresses(s, j + 1, ip);
                ip.pop_back();
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        vector<int> ip;
        restoreIpAddresses(s, 0, ip);
        return m_res;
    }
};