[Leetcode]93. Restore IP Addresses(C++)

题目描述

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.

例子

例子 1

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

例子 2

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

例子 3

Input: s = "1111" Output: ["1.1.1.1"]

Follow Up

Note

Constraints

0 <= s.length <= 3000

s consists of digits only.

解题思路

这道题采用回溯法的思路，假设一开始初始化空 IP，从前往后遍历字符串 s，在遍历每一位 num 时我们有两种选择：

将该位置的数字加到 IP 地址当前最后一位的数字上（IP.back() * 10 + num）
或者将该位置加到 IP 地址的新一位（IP.push_back(num)）

针对这两种情况有以下情况可以剪枝：

当前 IP 为空或者最后的数字为 0 时，只能执行第一种选择
当 IP 长度超过 4 个数字可以直接返回（针对第一种选择的结果）
当 IP 最后一位数字大于 255 时可以直接返回（针对第二种选择的结果）

遍历到字符串结尾时，只有 IP 恰好为 4 个数字的情况才将其转为字符串压入结果中。

代码如下：

#include <string>
#include <vector>

class Solution {
public:
    std::vector<std::string> restoreIpAddresses(std::string s) {
        std::vector<int> current_ip;
        std::vector<std::string> ip_list;
        iterate(s, 0, current_ip, ip_list);
        return ip_list;
    }

private:
    void iterate(const std::string& s, int idx, std::vector<int>& current_ip,
                 std::vector<std::string>& ip_list) {
        if (current_ip.size() > 4 ||
            (!current_ip.empty() && current_ip.back() > 255)) {
            return;
        }

        if (idx == s.length()) {
            if (current_ip.size() == 4) {
                std::string ip = "";
                for (int i = 0; i < 3; i++) {
                    ip += std::to_string(current_ip[i]);
                    ip += ".";
                }
                ip += std::to_string(current_ip[3]);
                ip_list.push_back(ip);
            }
            return;
        }

        // option 1: add new digit to next position
        int num = s[idx] - '0';
        current_ip.push_back(num);
        iterate(s, idx + 1, current_ip, ip_list);
        current_ip.pop_back();

        // option 2: add new digit to current position only when current
        // position is not empty or 0
        if (!current_ip.empty() && current_ip.back() != 0) {
            current_ip.back() *= 10;
            current_ip.back() += num;
            iterate(s, idx + 1, current_ip, ip_list);
            current_ip.back() /= 10;
        }
    }
};

时间复杂度: O(n!)
空间复杂度: O(n!)

GitHub 代码同步地址： 93.RestoreIpAddresses.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions