leetcode93. Restore IP Addresses

最新推荐文章于 2025-03-02 21:39:48 发布

Coding_Reading

最新推荐文章于 2025-03-02 21:39:48 发布

阅读量384

点赞数

分类专栏： C++ 字符串

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/77840801

版权

C++ 同时被 2 个专栏收录

17 篇文章

订阅专栏

字符串

8 篇文章

订阅专栏

本文介绍了一种使用回溯法解决IP地址恢复问题的中等难度算法。通过递归地尝试所有可能组合，并利用剪枝技术减少计算量，确保每个部分的数值不超过256且符合IP地址规范。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

难度：medium

题目：

这里写图片描述

IP 地址是一个32位的整数，每8位的十进制组成一个数，用 . 分隔

很明显是一个回朔法的题，特别注意的是遇到0时的情况，还有每个数值要小于256，进行剪枝减小运算量

AC解：

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int len = s.length();
        vector<string> v;
        vector<string> temp;
        backTrack(v, temp, s, 0, len);
        return v;
    }

    void backTrack(vector<string>& v, vector<string>& temp, string& s,
                  int start, int len) {
        if (start == len && temp.size() == 4) {
            v.push_back(temp[0] + "." + temp[1] + "."
                       + temp[2] + "." + temp[3]);
            return;
        }

        if (len - start > (4 - temp.size()) * 3)
            return; //剪枝
        if (len - start < (4 - temp.size()))
            return; //剪枝

        int sum = 0;
        for (int i = start; i < len && i < start + 3; i++) {
            sum = 10 *sum + s[i] - '0';
            if (sum > 255) return;  //剪枝
            temp.push_back(s.substr(start, i - start + 1));
            backTrack(v, temp, s, i + 1, len);
            temp.pop_back();
            if (sum == 0) return;   //剪枝
        }
    }
};