题解 | #数字字符串转化成IP地址#TOP74

一个ip组有四组，每一组可以选1到3个数。第一组先选一个数，剩下给后面选，每次记录下组的字符串下标。递归+回溯

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<>();
        dfs(0, 0, new StringBuilder(), result, s);
        return result;
    }
    //index : 每一组开头的下标
    private void dfs(int index, int depth, StringBuilder ip,
                     ArrayList<String> result, String s) {
        int length = ip.length();
        if (index== s.length() && depth == 4) {
            ip.deleteCharAt(length - 1);
            result.add(ip.toString());
            return;
        }
        for(int i = 1 ;i <= 3;i++){
            //边界 下标超出字符串长度
            if(i + index > s.length()){
                break;
            }
            int num = Integer.parseInt(s.substring(index, index + i));
            
            if(num > 255 || String.valueOf(num).length() != i){
                continue;
            }
            
            ip.append(num).append(".");
            dfs(index + i, depth + 1, ip ,result, s);
            ip.setLength(length);
        }
    }

}