Restore IP Addresses

 Total Accepted: 31755 Total Submissions: 151676My Submissions

Question Solution 

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)

分析：将字符串切割转化成有效地IPv4地址的形式，我们的方法就是找到有效3个分割点，也就是sp1,sp2和sp3，每个子片段有效尺寸1~3，在尺寸外的不考虑

public class Solution {

    public List<String> restoreIpAddresses(String s) {

        List<String> x=new ArrayList<String>();

        int l=s.length();

        if(l<4)

            return x;

        int sp1=0;

        int sp2=0;

        int sp3=0;

        for(sp1=1;sp1<=3;sp1++)

            for(sp2=sp1+1;sp2<=sp1+3;sp2++)

                for(sp3=sp2+1;sp3<=sp2+3;sp3++)

                {

                    if(l-sp3>0&&l-sp3<4)

                    {

                        //if()

                        String s1=s.substring(0,sp1);

                        String s2=s.substring(sp1,sp2);

                        String s3=s.substring(sp2,sp3);

                        String s4=s.substring(sp3,l);

                        

                        if(s1.length()>1&&s1.charAt(0)=='0')

                            continue;

                        if(s2.length()>1&&s2.charAt(0)=='0')

                            continue;

                        if(s3.length()>1&&s3.charAt(0)=='0')

                            continue;

                        if(s4.length()>1&&s4.charAt(0)=='0')

                            continue;

                            

                        int d1=Integer.parseInt(s1);

                        if(d1>255)

                            continue;

                        int d2=Integer.parseInt(s2);

                        if(d2>255)

                            continue;

                        int d3=Integer.parseInt(s3);

                        if(d3>255)

                            continue;

                        int d4=Integer.parseInt(s4);

                        if(d4>255)

                            continue;

                        x.add(s1+"."+s2+"."+s3+"."+s4);

                    }

                }

        return x;

    }

}