C++ Implementation using backtrack (very intuitive and easy to understand)


  • 0
    A
    class Solution {
    public:
        void dfs(int start, string& s, vector<string>& tmp, vector<vector<string>>& res) {
            if (start == s.size()) {
                if (tmp.size() == 4)
                    res.push_back(tmp);
                return;
            }
            for (int i=start;i<s.size()&&i<=start+2;i++) {
                if (isValid(s.substr(start, i-start+1))) { // If current part (s[start~i]) is valid, move on to the next DFS step (starting from index i+1)
                    tmp.push_back(s.substr(start, i-start+1));
                    dfs(i+1, s, tmp, res);
                    tmp.pop_back(); // Destroy the last valid section, extend and check it in the next for loop
                }
            }
        }
        bool isValid(string s) { // Only 1~3 digits are valid, and for 3-digits, it should fall between 0~255
            switch(s.size())  {
                case 1:
                    return true;
                    //break;
                case 2:
                    if (s[0]!='0')
                        return true;
                    //break;
                case 3:
                    if (s[0]!='0' && s<="255" && s>="100")
                        return true;
                    //break;
                default:
                    return false;
                    //break;
            }
        }
        vector<string> restoreIpAddresses(string s) {
            vector<vector<string>> res;
            vector<string> tmp;
            vector<string> ret;
            if (s.size() < 4 || s.size()>12)
                return ret;
            dfs(0, s, tmp, res);
            for (int i=0;i<res.size();i++) { // Format the final result (from vector to string, and insert delimiter '.')
                string str = res[i][0];
                for (int j=1;j<res[i].size();j++)
                    str += ("." + res[i][j]);
                ret.push_back(str);
            }
            return ret;
        }
    };
    

Log in to reply
 

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