LeetCode: 93. Restore IP Addresses

题目描述

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

题目大意： 将给定的字符串数字转换成有效的点十分 IP 地址。需要输出所有可能的情况。

解题思路 —— 深度搜索(DFS)

深度搜索遍历可能的情况，然后判断其有效性。

AC 代码

class Solution {
private:
    // 用字符串 s 的 [beg, end) 区间拼凑出 curIpAddr 的所有可能
    // 并将其存入 ipAddrs中.
    void restoreIpAddressesRef(string s, int beg, int end, vector<string>& curIpAddr, vector<string>& ipAddrs)
    {
        // 无效地址
        if(curIpAddr.size() > 4) return;

        // 有效地址
        if(curIpAddr.size() == 4 && beg == end)
        {
            string addr = curIpAddr[0];
            for(int i = 1; i < 4; ++i)
            {
                addr += ("." + curIpAddr[i]);
            }
            ipAddrs.push_back(addr);
            return;
        }

        string curAddrPart;
        for(int i = beg; i < end && i - beg < 3; ++i)
        {
            curAddrPart.push_back(s[i]);

            // 除 0 以外， 不能有前置 0, 如："010010" 不能是 01.0.01.0
            // 地址段不能大于 255
            if((s[beg] == '0' && i != beg) || stoi(curAddrPart) > 255) break;

            // 查找下一个地址段
            curIpAddr.push_back(curAddrPart);
            restoreIpAddressesRef(s, i+1, end, curIpAddr, ipAddrs);
            curIpAddr.pop_back();
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> curIpAddr, ipAddrs;
        restoreIpAddressesRef(s, 0, s.size(), curIpAddr, ipAddrs);

        return ipAddrs;
    }
};