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

import java.util.*;


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

    private void backTrace(String s, int index, ArrayList<String> sb) {
        if (index == s.length()) {
            if (sb.size() == 4) {
                StringBuilder str = new StringBuilder();
                for (int i=0; i<sb.size(); i++) {
                    str.append(sb.get(i));
                    str.append(".");
                }
                str.deleteCharAt(str.length()-1);
                ans.add(str.toString());
            }
            return;

        }
        
        for (int j=1; j<=3; j++) {
            if (j + index > s.length()) break; 
            String sub = s.substring(index, index+j); // 构造子串
            if (!valid(sub)) continue;
            sb.add(sub);
            backTrace(s, index+j, sb);
            sb.remove(sb.size()-1);
        }
    }

    private boolean valid(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        int number = 0;
        for (int i=0; i<s.length(); i++) {
            int digit = s.charAt(i) - '0';
            number = number * 10 + digit;
        }
        return number >= 0 && number <= 255;
    }
}