C++ Simple Solution, Concise Code


  • 0
    class Solution {
        bool IsValid(string& str) {
            if (str.empty() || str.size() > 3 || str.size() > 1 && str[0] == '0' || stoi(str) > 255)
                return false;
            return true;
        }
        void dfs(string& s, string str, int index, int cnt, vector<string>& res) {
            if (cnt == 3) { // 3 dots
                string end = s.substr(index);
                if (IsValid(end)) {
                    res.push_back(str + '.' + end);
                }
                return;
            }
            
            // every block has 1-3 digit
            for (int i = 1; i <= 3 && index + i < s.size(); i++) {
                string block = s.substr(index, i);
                if (IsValid(block)) {
                    dfs(s, str + (index ? "." : "") + block, index + i, cnt + 1, res);
                }
            }
        }
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> ret;
            dfs(s, "", 0, 0, ret);
            return ret;
        }
    };
    

Log in to reply
 

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