本文共 3047 字，大约阅读时间需要 10 分钟。

LeetCode刷题：93. Restore IP Addresses

原题链接：

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

这个题目的意思是给定一个字符串，分解出所有有可能的合法的IP地址的组合。

问题分析

有效的IP地址形式: 1.1.1.1 可以划分为4段，

这个问题如果采用DFS算法求解，解题思路如下：

边界条件，对于目标字符串sTarget来说：

if (sTarget == null || sTarget.length() <= 0 || sTarget.length() < 4 || sTarget.length() > 12) {            //返回            return ANSWER;        }

算法设计

package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.List;public class RestoreIPAddressDemo3 {
       /*     * 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)     */    /*     * DFS算法     *      */    // 深度优先遍历，DFS即可实现，用ANSWER保存结果    List
   
     ANSWER = new ArrayList
    
     ();    public List
     
       restoreIpAddresses(String s) {        /*         * 有效的IP地址形式: 1.1.1.1 可以划分为4段，         * 每段从0-255,例如 255.255.255.255 是有效的IP地址         * 这样的话，不计算分隔符点位（.），组成一个有效的IP地址最少需要4位；         * 最大是12位 给出下面的判断条件处理各种不同的错误情况         */        if (s == null || s.length() <= 0 || s.length() < 4 || s.length() > 12) {            //返回            return ANSWER;        }        String tmp = "";        // 调用DFS算法，并传入了4个参数        dfsIPAddress(s, 0, 0, tmp);        //返回        return ANSWER;    }    // index 记录开始的位置，k记录截取的数量，s为目标字符串    void dfsIPAddress(String s, int index, int k, String tmp) {        //设置边界条件        if (k == 3) {            String t = s.substring(index, s.length());            //判断是否符合合法的IP地址规则            if (check(t))                //添加到结果中                ANSWER.add(tmp + t);            return;        } else {            // 每一次最长的截取长度是i，最短1位，最长3位            for (int i = 1; i <= 3 && index + i < s.length(); i++) {                String t = s.substring(index, index + i);                if (check(t))                    dfsIPAddress(s, index + i, k + 1, tmp + t + ".");            }        }    }    //IP地址检查    public boolean check(String ip) {        // 以0开始的字符串，只有0是合理的，其余的比如001等等都不是合理的        if (ip.charAt(0) == '0') {            if (ip.equals("0"))                return true;            else                return false;        } else {            int ipNum = Integer.parseInt(ip);            //整数范围在0-255之间，合法            if (ipNum > 0 && ipNum <= 255)                return true;            else // 非法的IP地址段数值范围                return false;        }    }    public static void main(String[] args) {        // TODO Auto-generated method stub        RestoreIPAddressDemo3 restoreIP = new RestoreIPAddressDemo3();        String str = "25525511135";        List
      
        ipList = restoreIP.restoreIpAddresses(str);        System.out.println(ipList);    }}
      
     
    
   

运行结果：

[255.255.11.135, 255.255.111.35]

（完）

转载地址：http://ewtdi.baihongyu.com/