An iterative C++ solution using BFS


  • 0
    G
    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            int n = (int)s.length();
            list<pair<int, string>> addrs; // a list of {the next index, addr}
            addrs.push_back({0, ""});
            
            for (int i = 0; i < 4; ++i) {
                int m = (int)addrs.size();
                for (int j = 0; j < m; ++j) {
                    auto addr = addrs.front();
                    addrs.pop_front();
                    string cur = "";
                    for (int k = 0; k + addr.first < n && k < 3; ++k) {
                        cur.push_back(s[addr.first + k]);
                        int remain = n - 1 - (addr.first + k);
                        
                        // pruning
                        if ((k > 0 && cur[0] == '0') || (k == 2 && stoi(cur) > 255) || (remain < 3 - i)) 
                            break;
                        if (remain > (3 - i) * 3)
                            continue;
    
                        string new_addr = addr.second + (addr.second.empty() ? "" : ".") + cur;
                        addrs.push_back({addr.first + k + 1, new_addr});
                    }
                }
            }
            int m = (int)addrs.size();
            vector<string> results(m);
            for (auto it = addrs.rbegin(); it != addrs.rend(); ++it)
                results[--m] = it->second;
            
            return results;
        }
    };
    

Log in to reply
 

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