首页 > 其他 > 详细

LeetCode Restore IP Addresses

时间:2014-07-06 16:03:02      阅读:338      评论:0      收藏:0      [点我收藏+]
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ips;
        vector<int> ip;
        dfs(s, 0, ip, ips);
        return ips;
    }
    
    void dfs(string& s, int pos, vector<int>& ip, vector<string>& ips) {
        int len = s.length();
        int fid = ip.size();
        if (len == pos) {
            if (fid == 4) {
                ips.push_back(intip2str(ip));
            }
            return;
        }
        
        if (3 * (4 - fid) < len - pos) return;  // avoid TL
        
        int cur = 0;
        for (int i=pos; i<len && i < pos+3; i++) {
            if (i != pos && cur == 0) break;   // no leading zero in ip addr
            cur = cur * 10 + s[i] - 0;
            if (cur > 255) break;
            ip.push_back(cur);
            dfs(s, i + 1, ip, ips);
            ip.pop_back();
        }
    }
    
    string intip2str(vector<int> &ip) {
        if (ip.size() != 4 ) {
            return "format error. number of fields should be 4";
        }
        string strip;
        for (int i=0; i<4; i++) {
            strip.append(to_string(ip[i]));
            strip.append(i==3 ? "" : ".");
        }
        return strip;
    } 
};

反正ip地址数字不过直接dfs,不过也要稍微剪枝一下,前导零不能使用

LeetCode Restore IP Addresses,布布扣,bubuko.com

LeetCode Restore IP Addresses

原文:http://www.cnblogs.com/lailailai/p/3825396.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!