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

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<>();
        dfs(s, 0, 0, ans);
        return ans;
    }
    String num = "";
    private void dfs(String s, int pos, int cnt, ArrayList<String> ans){
        if(cnt == 4){
		  // 已经分割出4个数字，但是字符串的字符还未使用完，肯定不行
            if(pos != s.length())return;
            ans.add(num);
        }
        String cur = ""; // 当前分割得到的数字
        for(int i = pos; i < pos+3 && i < s.length(); i++){ // 注意边界条件，每个数字长度不超过3位，且遍历的i不超过字符串长度
            cur += s.charAt(i);
            int x = Integer.parseInt(cur);
            if(x <= 255 && (cur.length()==1 || cur.charAt(0) != '0')){ // 只有一位时可为0，否则不能有前导0
                String temp = num;
                num += cur;
                if(cnt != 3)num += '.'; // 最后一个数字后面没有.
                dfs(s, i+1, cnt+1, ans);
                num = temp; // 回溯
            }
        }
    }
}

使用回溯解决