93. Restore IP Addresses

backtracking O(27) time 即O(3⁴)
每一段都有3种可能，总共4段，遍历所有可能即为27种

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        dfs(s, "", 4);
        return res;
    }

    void dfs(string_view s, string &&a, int dots) { // 这里a用的value copy省事
        if (dots == 0) {
            if (s.empty()) { // 如果s不为空说明输入的字符串过长
                a.pop_back();
                res.push_back(a);
            }
            return;
        }
        string str;
        for (int i = 0; i < min((int)s.length(), 3); ++i) {
            str += s[i];
            if (str.length() > 1 && str[0] == '0') break; // 检查合法性
            if (stoi(str) > 255) break;
            dfs(s.substr(i + 1), a + str + '.', dots - 1); // 这里append str以后不好弹出来实现回溯，所以直接用value copy就不弹出了
        }
    }

    vector<string> res;
};