Concise C++ DFS code, easy to understand


  • 0
    L
    class Solution {
    public:
        bool check(string s) {
            if (s.size() > 1 && s[0] == '0') return false;
            int num = stoi(s, nullptr, 0);
            return num < 256;
        }
        
        bool checkPoint(string s) {
            int count = 0;
            for(int i = 0; i < s.size(); i++) {
                if (s[i] == '.') {
                    count++;
                }
            }
            return count == 3;
        }
        
        vector<string> processIP(vector<string> vec) {
            vector<string> res;
            for (int i = 0; i < vec.size(); i++) {
                if (checkPoint(vec[i])) res.push_back(vec[i]); 
            }
            return res;
        }
        
        vector<string> DFS(string s) {
            vector<string> res;
            if (s.empty() || s.size() > 12) return res;
            for (int i = 1; i < 4 && i <= s.size(); i++) {
                string pre = s.substr(0, i);
                if (check(pre)) {
                    vector<string> tmp = DFS(s.substr(i));
                    if(!tmp.empty()) {
                        for(int j = 0; j < tmp.size(); j++) {
                            //tmp[i] = pre + "." + tmp[i];
                            res.push_back(pre + "." + tmp[j]);
                        }
                    } else {
                        res.push_back(pre);
                    }
                    
                }
            }
            return res;
        }
        
        vector<string> restoreIpAddresses(string s) {
            return processIP(DFS(s));
        }
    };
    

Log in to reply
 

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