動機

要複習一下怎麼用C++

Problem

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. 

 

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: s = "010010"Output: ["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

 

Constraints:

    t
  • 0 <= s.length <= 3000
    • t
  • s consists of digits only.

Sol

題外話: 原來multiset就是sortedlist

class Solution {
public:
    void bt(string&& s, int seg, string acc, vector<string>& ret) {
        if (seg == 5) {
            if (s.empty())
                ret.push_back(acc.substr(0,acc.size()-1)); // remove dot
        } else {
            for (auto& len : {1, 2, 3}) {
                if (s.size() >= len) {
                    string net = s.substr(0,len);
                    if (stoi(net) <= 255 && (net[0] != '0' || net == "0"))
                        bt(s.substr(len),seg+1,acc+net+".",ret);
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s, int seg=1) {
        vector<string> ret;
        bt(move(s),1,"",ret);
        return ret;
    }
};