LeetCode：复原IP地址【93】

题目描述

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

示例:

　　输入: "25525511135"

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

题目分析

　　ip地址由三个小数点（.）分割成四段，每一段取值为0~255。所以输入字符串s最长为12，最少为4位。

　　以2556....来划分的话，第一段有可能是下面三种情况：

255，此段为3个

25，此段为2个

2，此段为1个

　　所以采用递归框架，从某一位置开始，往后依次截取3、2、1，但是如果某一段截取到的情况是下面两种则不用继续深入：

>255，大于255此段不合适，说明此段不应该截取长度为3。

0XX或0X，如果此段为0开头，是不合理，说明此段不应该截取长度为3或2，只能为1，即0作为单独一段。

　　即剪枝条件：不能以0开头，不能大于255.

Java题解

class Solution {    public List
     
       restoreIpAddresses(String s) {        List
      
        result = new ArrayList<>();        if(s.length()>12||s.length()<4)            return result;        digui(result,s,0,0);        return result;    }        public void digui(List
       
         list,String tmp,int pos,int count){        //结束条件        if(count==3){            if(pos+3>tmp.length()-1&&isValid(tmp.substring(tmp.lastIndexOf(".")+1)))                list.add(tmp);        }        //业务处理        if(pos+3
        
         255)            return false; 　　　　　//用于处理0XX或0X的情况        if(!String.valueOf(val).equals(s))            return false;        return true;    }}

思考

　　暴力通常可以解决问题，但是肯定不是最高效的方法，这里对字符串的处理占用了太多内存和时间。有没有更好的办法呢？

　　待续...

转载于:https://www.cnblogs.com/MrSaver/p/11610149.html

你可能感兴趣的文章