Restore IP Addresses 426

Question

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

Example

Given "25525511135", return

[ "255.255.11.135",

"255.255.111.35" ]

Order does not matter.

Solution

这道题其实是将字符串分割成4段，使得结果为合法的IP地址。要求返回所有合法IP地址，想到用递归。

合法的IP地址为：1）由4段组成 2）每一段长度为1到3 3）每一段如果不是0，不能以0开头，如01，00 4）每一段大小不能大于255

1. 用一个result记录合法答案，用一个list纪录当前答案，start代表能够取值的起始位置。

2. 当前段可以取start~start，start~start＋1，start~start＋2这几个字符串，然后递归求下一段。每次取值要检验取的字符串的合法性。

3. 当取满4段时，看此时是否还有字符串剩下，没有则将4段拼成合法的IP地址

代码如下：

public class Solution {
    /**
     * @param s the IP string
     * @return All possible valid IP addresses
     */
    public ArrayList<String> restoreIpAddresses(String s) {
        // Write your code here
        ArrayList<String> result = new ArrayList<String>();
        if(s == null || s.length() == 0){
            return result;
        }

        ArrayList<String> list = new ArrayList<String>();
        helper(s, result, list, 0);
        return result;
    }

    private void helper(String s, ArrayList<String> result, ArrayList<String> list, int start){
        if(list.size() == 4){
            //分成4段后若还有字符串剩余则不合法
            if(start != s.length()){
                return;
            }
            //每一段后面加"."，再将最后一个"."删去
            StringBuilder sb = new StringBuilder();
            for(String str : list){
                sb.append(str);
                sb.append(".");
            }
            sb.deleteCharAt(sb.length() - 1);
            result.add(sb.toString());
            return;
        }

        for(int i = 1; i <= 3 && start + i <= s.length(); i++){
            //每一段长度不能超过3，同时如果超过了1位，则不能以0开头，如01
            if(i != 1 && s.charAt(start) == '0'){
                break;
            }
            //如果该段为3位，则要检验是否超过255
            if(i == 3 && !isValid(s.substring(start, start + 3))){
                break;
            }

            String temp = s.substring(start, start + i);
            list.add(temp);
            helper(s, result, list, start + i);
            list.remove(list.size() - 1);
        }
    }

    //合法IP的每一段都小于等于255
    private boolean isValid(String s){

        if(Integer.valueOf(s) > 255){
            return false;
        }
        return true;
    }
}