【一天一道LeetCode】#93. Restore IP Addresses

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处

(一)题目

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地址

解题过程中需要注意无效ip,诸如00,010等

解题思路:采用回溯法,ip有四级,分别判断每一级是否为有效的,依次递归,到最后判断能不能组成有效ip,没有就回溯到上一级继续递归。详细思路见代码注释

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        string ip;
        dfsRestoreIp(s,ip,0,0,ret);
        return ret;
    }
    void dfsRestoreIp(string& s , string ip , int count , int i ,vector<string>&ret)
    {
        if(count==4)//计数到4后表示一个ip地址
        {
            if(i==s.length()) {
                ip.erase(ip.end()-1);//去除最后的'.'
                ret.push_back(ip);
            }
            return;
        }
        int num = 0;
        for(int j = i ; j < s.length() ; j++)
        {
            ip+=s[j];
            num = num*10+(s[j]-'0');
            if(num>0&&s[i]=='0') return;//去除诸如‘01’,‘010’等无效ip
            if(num==0&&j-i>=1) return;//去除诸如'00'等无效ip
            if(num<256)
            {
                ip+='.';//加上.代表到下一级
                dfsRestoreIp(s,ip,count+1,j+1,ret);
                ip.erase(ip.end()-1);//回溯到上一级
            }
            else return;
        }
    }
};

推荐文章

实体框架持久化计算列问题

实体框架持久化计算列问题

推荐文章

ActionScript:将同一swf文件的多个实例添加到stage

ActionScript:将同一swf文件的多个实例添加到stage

推荐文章

java中对web服务的Http请求

java中对web服务的Http请求

推荐文章

如何在sql server中的一系列xml文档(varchar列类型)中插入新节点

如何在sql server中的一系列xml文档(varchar列类型)中插入新节点

推荐文章

显示全年的ASP.NET可用性日历

显示全年的ASP.NET可用性日历

推荐文章

无法从AsyncFIleUpload.OnUploadCompleted代码隐藏访问.NET控件

无法从AsyncFIleUpload.OnUploadCompleted代码隐藏访问.NET控件

推荐文章

数据库列检查PK并覆盖另一列

数据库列检查PK并覆盖另一列

推荐文章

如何在GWT-RPC中触发onFailure?

如何在GWT-RPC中触发onFailure?

推荐文章

给定整数集的子集,其和为常数N:Java

给定整数集的子集,其和为常数N:Java

推荐文章

如何用布尔条件编写JPA查询

如何用布尔条件编写JPA查询

推荐文章

如何组合eclipse的所有包?

如何组合eclipse的所有包?

推荐文章

uNhAddIns足够活跃吗?

uNhAddIns足够活跃吗?

推荐文章

谷歌分析单页订单

谷歌分析单页订单

推荐文章

UIImagePickerController的正确释放

UIImagePickerController的正确释放

推荐文章

将文件夹复制到另一个以递归方式复制所有内容的文件夹

将文件夹复制到另一个以递归方式复制所有内容的文件夹

推荐文章

如何在命名空间作用域中选择元素并在输出中去掉空的默认命名空间

如何在命名空间作用域中选择元素并在输出中去掉空的默认命名空间