93 - Restore IP Addresses

#medium

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

• For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

class Solution {
public:
    vector<string> result;

    // 判斷字符串s在左閉又閉區間[start, end]所組成的數字是否合法
    bool isValid( string s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0開頭的數字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非數字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大於255了不合法
                return false;
            }
        }
        return true;
    }

    void backtracking( string s, int startIndex, int pointSum ) {
        // startIndex: 搜索的起始位置，pointNum:添加逗點的數量
        if ( pointSum == 3 ) {
            // 判斷第四段子字符串是否合法，如果合法就放進result中
            if ( isValid( s, startIndex, s.size() - 1) ) {
                result.push_back( s );
            }
            return;
        }

        for ( int i = startIndex; i < s.size(); i++ ) {
            // 判斷 [startIndex,i] 這個區間的子串是否合法，startIndex固定，i繼續向後移動
            if ( isValid( s, startIndex, i) ) {
                s.insert( s.begin() + i + 1, '.' ); // 在i的後面插入一個逗點
                pointSum++;
                backtracking( s, i + 2, pointSum);  // 插入逗點之後下一個子串的起始位置為i+2
                pointSum--;
                s.erase(s.begin() + i + 1 ); // 回溯刪掉逗點
            }
            else break;

        }

    }

    vector<string> restoreIpAddresses(string s) {
        backtracking( s, 0, 0 );
        return result;
    }
};