[C++] Clean code beats 85%


  • 0
    H
    class Solution {
    public:
        bool isValid(const string &s, int start, int end) {
            if (end >= start && end < start + 3 && (s[start] != '0' || start == end)) {
                int val = 0;
                while (start <= end) {
                    val = val * 10 + s[start] - '0';
                    ++start;
                }
                return (val <= 255);
            }
            return false;
        }
    
        vector<string> restoreIpAddresses(string s) {
            vector<string> res;
            int size = s.size();
            if (size < 4) return res;
            
            for (int i = 0; i < size - 3 && i < 3; ++i) {
                if (size - i > 10) continue;
                for (int j = i + 1; j < size - 2 && j < i + 4; ++j) {
                    if (size - j > 7) continue;
                    for (int k = j + 1; k < size; ++k) {
                        if (size - k > 4) continue;
                        if (isValid(s, k + 1, size - 1) && isValid(s, j + 1, k) && isValid(s, i + 1, j) && isValid(s, 0, i)) {
                            string t = s;
                            t.insert(t.begin() + i + 1, '.');
                            t.insert(t.begin() + j + 2, '.');
                            t.insert(t.begin() + k + 3, '.');
                            res.push_back(t);
                        }
                    }
                }
            }
            return res;
        }
    };
    

    This idea credit to https://discuss.leetcode.com/topic/3919/my-code-in-java/2


Log in to reply
 

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