第93题：复原IP地址

一．问题描述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"

输出: ["255.255.11.135", "255.255.111.35"]

二．解题思路

本题思路：采用回溯算法进行求解，建立递归函数（全局变量list存储IP地址，局部变量data存储剩下的字符串，length存储当前需要填的位数，数组nums存储ip中各个段的值）

步骤一：建立递归函数，判断，当nums数组最后一位数组满足要求则将数组按照格式要求存储到list中，否则，进入步骤二。

步骤二：进行回溯算法，依次从data中取出数字，判断其是否小于256且大于等于0，则将其添加到nums[length]中，在data中删除该数字，继续递归，返回步骤一。

步骤三：这道题需要注意细节，00，001这种情况和数字的界限问题，所以要考虑周全。

三．执行结果

执行用时 :3 ms, 在所有 java 提交中击败了89.68%的用户

内存消耗 :36.3 MB, 在所有 java 提交中击败了48.81%的用户

四． Java代码

class Solution {

    public List<String> restoreIpAddresses(String s) {

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

        int []nums= {-1,-1,-1,-1};

        address(list,s,0,nums);

        return list;

    }

    public void address(List<String> list,String data,int length,int []nums) {

        if(nums[3]<256&&nums[3]>=0&&data.length()<=0){

            String temp="";

            for(int i=0;i<4;i++) {

                temp=temp+nums[i];

                if(i<3)

                temp=temp+".";

            }

            list.add(temp);

        }

        if(length==4&&data.length()>=4){

            return;

        }

        String tem="";

        for(int j=0;j<3&&j<data.length()&&length<4&&data.length()>0;j++){

            tem=tem+data.charAt(j);

            int temdata=Integer.parseInt(tem);

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

                continue;

            }

            if(temdata<256&&temdata>=0) {

                String getdata=data.substring(j+1,data.length() );

                int []num= {-1,-1,-1,-1};

                System.arraycopy(nums, 0, num, 0, num.length);

                num[length]=temdata;

                address(list,getdata,length+1,num);

            }

        }

    }

}

巴特西

第93题：复原IP地址

最新文章

热门文章