【Leetcode】93. Restore IP Addresses（模拟）（2019年美团无人驾驶算法实习面试原题）

Love The Way You Lie 2022-02-21 10:59 124阅读 0赞

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"]

题目大意：

给出一个string找出其中能够组成合法IP地址的组合。

解题思路：

合法的string长度在4到12之间，直接遍历次数也不多，可以直接遍历搜索。

faster than 100%

class Solution {
    private:
        vector<string> ans;
        bool valid(string a){
            if(a.length()>1 && a[0]=='0'){
                return false;
            }
            return true;
        }
    public:
        vector<string> restoreIpAddresses(string s) {
            // str -> int
            // string str = "123";
            // int n = atoi(str.c_str());
            // cout<<n;
            
            if(s.length()<=3||s.length()>12){
                return ans;
            }
            
            int len = s.length();
            
            int i = 0;
            for(int j=1;j<4 && j<len-2;j++){
                for(int k=j+1;k<j+4 && k<len-1;k++){
                    for(int l=k+1;l<k+4 && l<len;l++){
    
                        
                        if(len-l>3) continue;
                        
                        string a = s.substr(i, j-i);
                        string b = s.substr(j, k-j);
                        string c = s.substr(k, l-k);
                        string d = s.substr(l, len-l);
      
                        if(valid(a)==false || valid(b)==false|| valid(c)==false || valid(d)==false) continue;      
                        int an = atoi(a.c_str());
                        int bn = atoi(b.c_str());
                        int cn = atoi(c.c_str());
                        int dn = atoi(d.c_str());
    
                        if(an>255||bn>255||cn>255||dn>255) continue;
                        string tmp=a+'.'+b+'.'+c+'.'+d;
                        
                        ans.push_back(tmp);
                    }
                }
            }  
            
            return ans;
        }
    };