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

貌似这个题是去年年底刷了，半天没写出来搁浅了？

WA了一次 没考虑0000

TLE了一次应该事先判断长度

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

Example:

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

 

class Solution {
public:
    vector<string> ans;
    void cal(int pos, int num, string &s, string pas) {//postion, . ,string, have return
        if(pos == s.length()) {
            if(num == 4){
                ans.push_back(pas.substr(1));
                cout<< pas;
            }
            return;
        }
        cal(pos+1, num+1,s , pas+"."+s.substr(pos,1));
        if(s[pos] != '0'){
            if(pos+1 < s.length())
                cal(pos+2, num+1, s, pas+"."+s.substr(pos,2));
            if(pos+2 < s.length() && (s[pos]-'0')*100 + (s[pos+1]-'0')*10 + (s[pos+2]-'0') < 256)
                cal(pos+3, num+1, s, pas+"."+s.substr(pos,3));
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.length()<=16 && s.length()>=4)
            cal(0, 0, s, string(""));
        return ans;
    }
};

哦 还有这种写法：

            string sub = s.substr(0, i);
            if(sub.size() > 1 && sub[0] == '0' || stoi(sub) > 255) break;