C++ 4ms BackTracking Solution with comments


  • 0
    L
    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> res;
            helper(s, 0, 4, "", res);
            return res;
        }
        
        void helper(string s, int pos, int count, string curr, vector<string>& res) {
            // count = 0 means all '.' has been added
            // pos = s.size() means has reached the end of the string
            if (count == 0 && pos == s.size()) {
                res.push_back(curr.substr(1));
                return ;
            }
            // '.' has been run out of but not reached the end so there is no correct answers
            if (count == 0) {
                return ;
            }
            
            // if the s[pos] = 0, the '.' has to be added directly after curr
            if (s[pos] == '0') {
                helper(s, pos + 1, count - 1, curr + ".0", res);
                return ;
            }
            int num = 0;
            for (int i = 0; i < 3 && pos + i < s.size(); i++) {
                num = num * 10 + s[pos + i] - '0';
                // as long as num is less than 255, add '.' and go to the next stage
                if (num <= 255) {
                    helper(s, pos + i + 1, count - 1, curr + '.' + s.substr(pos, i + 1), res);
                }
            }
        }
    };

Log in to reply
 

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