数字字符串转化成IP地址

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        // 算法：分支限界的递归回溯

        // 处理特殊情况：
        ArrayList<String> result = new ArrayList<>();
        if (s.length() < 4) {
            return result;
        }
        ArrayList<Integer> nums = new ArrayList<>();
        result = process(s, 0, nums);
        return result;
    }

    public ArrayList<String> process (String s, int i, ArrayList<Integer> nums) {
        int len = s.length();
        ArrayList<String> result = new ArrayList<>();
        // 递归出口
        if (nums.size() == 4 && i == len) {
            StringJoiner sj = new StringJoiner(".");
            for (Integer num : nums) {
                if (num >= 0 && num <= 255) {
                    sj.add(num.toString());
                } else {
                    // 划分错误
                    return null;
                }
            }
            result.add(sj.toString());
            return result;
        } else if (nums.size() == 4 && i < len) {
            // 划分错误
            return null;
        } else if (nums.size() < 4 && i == len) {
            // 划分错误
            return null;
        }

        // 递归分支 - 最多三种情况
        // 这里写的不太好，判断的逻辑全是“补丁”，但答案确实是对的
        for (int j = 1; j <= 3; j++) {
            if (i + j > len) {
                // 下标越界了，不必再往后划分了
                break;
            }
            String sub = s.substring(i, i + j);
            if (sub.length() > 1 && sub.startsWith("0")) {
                // 以0开头的多位数不合法，不必再往后划分了
                break;
            }
            int subNum = Integer.parseInt(sub);
            if (subNum > 255) {
                // 当前数超过255不合法，不必再往后划分了
                break;
            }
            nums.add(subNum);
            ArrayList<String> add = process(s, i + j, nums);
            if (add != null) {
                result.addAll(add);
            }
            // 注意恢复现场
            nums.remove(nums.size() - 1);
        }

        return result;
    }
}

List<List<String>> resList = new ArrayList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        backTrace(s, 0, new LinkedList<>());
        // 转格式
        return (ArrayList<String>)resList.stream().map(row -> String.join(".", row))
               .collect(Collectors.toList());
    }
    public void backTrace(String str, int i, LinkedList<String> tempList) {
        // ip固定为4组数字, 大于4的情况需要舍弃
        if (tempList.size() > 4) {
            return;
        }

        // 长度为4, 并且i已经走到字符串末尾, 则保存结果, 否则舍弃
        if (tempList.size() == 4) {
            if (i == str.length()) {
                resList.add(new ArrayList<>(tempList)); // 注意这里需要new ArrayList来深拷贝, 不然结果为空
            }
            return;
        }
        
        // 数字长度只能有三种情况, 即长度为1, 长度为2, 长度为3
        for (int k = 1; k <= 3; k++) {
            if (i + k > str.length()) break;
            String tempStr = str.substring(i, i + k);
            int tempNum = Integer.parseInt(tempStr);
            // 排除以0开头的, 并且长度大于1的情况, 如00, 001, 09 ...等等
            // 如果有0开头，那么必须是0本身才符合条件
            if (tempStr.startsWith("0") && tempStr.length() > 1) break;
            if (tempNum >= 0 && tempNum <= 255) {
                tempList.addLast(tempStr);
                backTrace(str, i + k, tempList);
                tempList.removeLast();
            }
        }
    }

public class Solution {
    public void recursion(List<String> result, String s, StringBuilder temp, int segmentCount, int index) {
        if (segmentCount == 4 && index == s.length()) {
            result.add(temp.toString());
            return;
        }
        if (segmentCount >= 4 || index >= s.length()) {
            return;
        }
        int currTempLength = temp.length();
        for (int i = 1; i <= 3 && index + i <= s.length(); i++) {
            String segment = s.substring(index, index + i);
            if (isValidSegment(segment)) {
                temp.append(segment);
                if (segmentCount < 3) {
                    temp.append(".");
                }
                recursion(result, s, temp, segmentCount + 1, index + i);
                temp.setLength(currTempLength);
            }
        }
    }

    public boolean isValidSegment(String segment) {
        if (segment.length() >= 2 && segment.charAt(0) == '0') {
            return false;
        }
        int num = Integer.parseInt(segment);
        return num >= 0 && num <= 255;
    }

    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return result;
        }
        recursion(result, s, new StringBuilder(), 0, 0);
        return result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here

        //先过滤掉不符合条件的
        if (s.length() < 4 || s.length() > 12) {
            return new ArrayList<>();
        }
        StringBuilder sb = new StringBuilder();
        ArrayList<String> res = new ArrayList<>();
        dfs(s, sb, res, 0, 0);
        return res;
    }

    public void dfs(String s, StringBuilder sb, ArrayList<String> res, int pointSum,
                    int start) {
        //如果逗号数量为3，则说明分割完成了
        if (pointSum == 3) {
            //再对最后一层循环的字符进行判断是否合法
            //左闭塞右开
            String sTemp = s.substring(start, s.length());
            if (isValid(sTemp)) {
                sb.append(sTemp);
                res.add(new String(sb.toString()));
                sb.delete(sb.length() - sTemp.length(), sb.length());
                // sb.setLength(sb.length() - sTemp.length());
                return;
            }

        }
        // 检查索引是否超出范围
        if (start >= s.length()) {
            return;
        }

        for (int i = start; i < s.length(); i++) {
            //截取的字符
            String sTemp = s.substring(start, i + 1);
            //判断是否合法
            if (!isValid(sTemp)) {
                //不合法就结束递归
                return;
            } else {
                // int lengthBeforeAppend = sb.length();
                sb.append(sTemp).append(".");
                pointSum++;
                dfs(s, sb, res, pointSum, i + 1);
                //记得删除逗号
                // sb.setLength(lengthBeforeAppend);
                sb.delete(sb.length() - sTemp.length() - 1, sb.length());
                pointSum--;
            }
        }

    }
    // 校验函数
    public boolean isValid(String s) {
        if (s.length() == 0 || (s.charAt(0) == '0' && s.length() != 1)) {
            return false;
        }
        int a = Integer.parseInt(s);
        return a >= 0 && a <= 255;
    }

}

ArrayList<String> res=new ArrayList<>();

int len=s.length();
// 左闭右开，校验偏移量
for(int i=1;i<4;i++){
    for(int j=i+1;j<i+4;j++){
        for(int k=j+1;k<j+4;k++){
            if(k>=len || k+3<len){
                continue;
            }
            String s1=s.substring(0 ,i);
            String s2=s.substring(i ,j);
            String s3=s.substring(j ,k);
            String s4=s.substring(k ,len);
            if(isOK(s1) && isOK(s2) && isOK(s3) && isOK(s4)){
                res.add(s1+"."+s2+"."+s3+"."+s4);
            }
        }
    }
}
return res;
}

public boolean isOK(String str){
    if(str.charAt(0)=='0' && str.length()>1){
        return false;
    }
    int num=Integer.parseInt(str);
    return num>=0 && num<=255;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    private String s;
    private ArrayList<String> ans=new ArrayList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
        this.s=s;
        dfs(new ArrayList<>(),0);
        return ans;
    }
    public void dfs(List<String> path,int idx){
        if(path.size()>=4){
            if(path.size()==4&&idx==s.length()){
                ans.add(convert(path));
            }
            return;
        }

        for(int i=idx+1;i<=s.length();i++){
            String si=s.substring(idx,i);
            int x=Integer.parseInt(si);
            if(s.charAt(idx)=='0'&&si.length()>1) break;
            if(x<=255&&x>=0){
                path.add(si);
                dfs(path,i);
                path.remove(path.size()-1);
            }else{break;}
        }
    }
    public String convert(List<String> path){
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<path.size();i++){
            if(i!=0) sb.append('.');
            sb.append(path.get(i));
        }
        return sb.toString();
    }
}

public class Solution {
    /**
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        List<Integer> list = new ArrayList<>();
        dfs(s, 0, list);
        return res;
    }

    ArrayList<String> res = new ArrayList<>();

    String getFromArray(List<Integer> list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
            if (i != list.size() - 1) {
                sb.append(".");
            }
        }
        return sb.toString();
    }

    void dfs(String s, int idx, List<Integer> list) {
        if (idx >= s.length()) {
            if (list.size() == 4) {
                res.add(getFromArray(list));
            }
            return;
        }
        if (list.size() >= 4) {
            return;
        }
        if (s.charAt(idx) == '0') {
            list.add(0);
            dfs(s, idx + 1, list);
            list.remove(list.size() - 1);
            return;
        }
        for (int i = idx; i < idx + 3 && i < s.length(); i++) {
            int temp = Integer.valueOf(s.substring(idx, i + 1));
            if (temp >= 0 && temp <= 255) {
                list.add(temp);
                dfs(s, i + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> ans=new ArrayList<>();
        build(s,0,0,ans);//startIndex,end
        return ans;
    }
    public void build(String s,int startIndex,int pointNum,ArrayList<String> ans){
        if(pointNum==3){
            if(isVaild(s,startIndex,s.length()-1)){
                ans.add(s);
            }
            return;
        }
        for(int i=startIndex;i<s.length();i++){
            if(isVaild(s,startIndex,i)){
                pointNum++;
                s=s.substring(0,i+1)+"."+s.substring(i+1);
                build(s,i+2,pointNum,ans);
                pointNum--;
                s=s.substring(0,i+1)+s.substring(i+2);
            }

        }

    }
    public boolean isVaild(String s,int startIndex,int end){
        if(startIndex>end){
            return false;
        }
        if(s.charAt(startIndex)=='0'&&startIndex!=end){
            return false;
        }
        int num=0;
        for(int i=startIndex;i<end+1;i++){
            if(s.charAt(i)>'9'||s.charAt(i)<'0'){
                return false;
            }
            num=num*10+s.charAt(i)-'0';
            if(num>255){
                return false;
            }
        }
        return true;

    }
}

import java.util.*;


public class Solution {
    /**
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        ArrayList<String> temp = new ArrayList<>();
        dfs(s, 0, res, temp);
        return res;
    }
    private void dfs(String s, int index, ArrayList<String> res,
                     ArrayList<String> temp) {
        if (temp.size() == 4) { //满足ip组数可能是结果
            if (index == s.length()) { //确实对s全部遍历过
                res.add(String.join(".", temp));
            }
            return;//没遍历过，不是解
        }
        for (int i = index; i < s.length() && i < index + 3; i++) {
            String sub = s.substring(index, i + 1); //截取字符串
            if (isCheck(sub)) {//符合ip规则
                temp.add(sub);
                dfs(s, i + 1, res, temp);
                temp.remove(temp.size() - 1);//回溯
            }
        }
    }

    private boolean isCheck(String sub) {
        if (sub.length() != 1 && sub.charAt(0) == '0')  return false;//前缀零
        int num = Integer.parseInt(sub);
        return num >= 0 && num <= 255;
    }
}

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> result = new ArrayList<>();
        restoreIpAddresses (s, result, "", 0);
        return result;
    }
    /**
     *
     * @param s 待处理的字符串
     * @param result    // 最终保存正确ip地址的集合
     * @param concat    // 拼接的合法ip地址
     * @param pointSum  // 标识当前处理的是第几段ip
     */
    public void restoreIpAddresses (String s, ArrayList<String> result, String concat,int pointSum) {
        if(s.length() == 0) return;

        // 表示当前查找第几段ip
        pointSum++;

        // 说明前三段已经找到了，该第四段，但是最后一段在这里判断就可以
        if(pointSum == 4){
            // 此处无需判断s字符串长度是否大于3，因为能递归到这里，s这个字符串的长度一定合法 (下面循环中做了处理)

            // 如果最后一段字符串s 转int大于255 或者 s字符串长度只要大于1，并且 首位字符是0，则不合法
            if(Integer.parseInt(s) > 255 || (s.length() > 1 && s.charAt(0) == '0')){
                return; // 结束，无需添加结果集
            }
            // 最后一段合法时，则拼接最后一段的字符串，添加结果集。
            // 这里substr 因为首次拼接时，小数点在首位，这里切割掉
            result.add(concat.substring(1) + "." + s);
            return;
        }

        // 已知每一段最多3位，所以只循环3次
        for (int i = 1; i < 4 && i <= s.length(); i++) {

            // 以i切割，left左字符串，right右字符串
            String left = s.substring(0, i); // left是切割的当前pointSum段的字符
            String right = s.substring(i);  // right是剩余未切割字符

            // pointSum 标识当前已经查找到了第几段
            // ip共四段，每一段最大3位。
            //      当pointSum为1的时候，后面的ip还剩3段，长度不能大于 3 * 3 = 9长度
            //      当pointSum为2的时候，后面的ip还剩2段，长度不能大于 3 * 2 = 6长度
            //      当pointSum为3的时候，后面的ip还剩1段，长度不能大于 3 * 1 = 3长度
            // 如果大于，则本次的切割可以认为无效， 下次循环继续向后切割
            if( (pointSum == 1 && right.length() > 9) || (pointSum == 2 && right.length() > 6) || (pointSum == 3 && right.length() > 3) ){
                continue;
            }

            // 如果切割后的左字符串 转int大于255 或者 左字符串长度只要大于1，并且 首位字符是0，则不合法
            if(Integer.parseInt(left) > 255 || (left.length() > 1 && left.charAt(0) == '0')){
                // 只要满足非法条件，可以直接return，因为下次循环只会分割的更大 或者 首位依旧还会是0
                return;
            }

            // 以上校验完毕后，说明当前pointNum段的字符串left合法
            // 那么将剩余字符right传入，并且将concat字符串参数，用.拼接left
            restoreIpAddresses (right, result, concat + "." + left,pointSum);
        }
    }
}

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    //找切割点 和 层数
    ArrayList<String> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        if (s.length() == 0) {
            return res;
        }
        process(s, 0);
        return res;
    }
    
    public void process(String s, int start) {
        if (path.size() > 4) {
            return;
        }
        if (path.size() == 4 && start == s.length()) {
            res.add(String.join(".", path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String cur = s.substring(start, i + 1);
            if (!isVaild(cur)) {
                continue;
            }
            path.add(cur);
            process(s, i + 1);
            path.removeLast();
        }
    }
    public boolean isVaild(String cur) {
        if (cur.charAt(0) == '0' && cur.length() > 1) {
            return false;
        }
        if (cur.length() > 3) {
            return false;
        }
        if (Integer.valueOf(cur) > 255) {
            return false;
        }
        return true;
    }
}

public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<>();
        if (s==null || s.length()<4) return res;
        backTrack(0,s,new ArrayList<>(),0,res);
        return res;
    }

    private void backTrack(int startIndex, String s, List<String> track,int depth,List<String> res) {
        // 递归终止
        if (startIndex>=s.length() && depth==4 && track.size()==4) {
            res.add(listToIpString(track));
            return;
        }
        // 剪枝
            // 1、最后一位长度大于3
        if (depth==3 && s.length()-startIndex>3) return;
            // 2、没有组成长度为 4 的 ip 地址
        if (depth<4 && startIndex>=s.length()) return;
        for (int i = 0; i < 3; i++) {
            int tailIndex = startIndex + i;
            if (tailIndex<s.length()) {
                String code = s.substring(startIndex, tailIndex + 1);
                if (isIpCode(code)) {
                    track.add(code);
                    backTrack(startIndex+code.length(),s,track,depth+1,res);
                    track.remove(track.size()-1);
                }
            }
        }
    }

    /**
     * 将回溯路径中的字符，组合成 String
     * @param list
     * @return
     */
    private String listToIpString(List<String> list) {
        StringBuilder builder = new StringBuilder();
        for (String elem : list) {
            builder.append(elem).append(".");
        }
        builder.deleteCharAt(builder.length()-1);
        return builder.toString();
    }

    /**
     * 判断当前数字是否符合 ip 规范
     * @param code
     * @return
     */
    private boolean isIpCode(String code) {
        // 0xx 这样的数是不合法的
        if (code.length()>1 && code.charAt(0)=='0') return false;
        Integer val = Integer.valueOf(code);
        return val>=0 && val<=255;
    }