LeetCode 93 Restore IP Addresses

    
        标签：
        
            回溯法
        
            LeetCode
        
    发布于：2022-03-27 09:11:30
    编辑于：2022-03-27 11:44:57
    浏览量：886

概述

https://leetcode.com/problems/restore-ip-addresses/

回溯法

class Solution {
public:
    vector<string> ans;
    vector<string> restoreIpAddresses(string s) {
        vector<string> path;
        backtrack(s, path, 0, 0);
        return ans;
    }
    
    void backtrack(string& s, vector<string>& path, int i, int n) {
        // cout << i << " " << n << endl;
        if (i > s.size()) return;
        if (n == 4 && i == s.size()) {
            ans.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
            return;
        }
        if (n == 4 || i == s.size()) return;
        
        path.push_back(s.substr(i, 1));
        backtrack(s, path, i + 1, n + 1);
        path.pop_back();
        
        if (s[i] != '0') {
            path.push_back(s.substr(i, 2));
            backtrack(s, path, i + 2, n + 1);
            path.pop_back();
            
            int v = stoi(s.substr(i, 3));
            if (v <= 255) {
                path.push_back(s.substr(i, 3));
                backtrack(s, path, i + 3, n + 1);
                path.pop_back();
            }
        }
    }
};

Links: leetcode-93-restore-ip-addresses