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

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        if (s.length() > 12) {
            return null;
        }
        StringBuilder sb = new StringBuilder(s);
        doRestoreIpAddresses(sb, 1);
        return ans;
    }
    
    ArrayList<String> ans = new ArrayList<>();

  	// 套用回溯算法模板
    public void doRestoreIpAddresses(StringBuilder s, int m) { // 回溯暴力算法，还要很多地方没有剪枝
        // write code here
        String[] nums = s.toString().split("\\.");
        if (nums.length > 4) { // 剪枝
            return;
        }
        if (validateIPv4(s.toString())) { // 结束条件
            ans.add(String.copyValueOf(s.toString().toCharArray()));
            return;
        }

        for (int i = m; i < s.length(); i++) { // 回溯
            s.insert(i, "."); 
            doRestoreIpAddresses(s, i + 2);
            s.replace(i, i + 1, "");

        }
    }
    
     public boolean validateIPv4(String IP) {
        String[] nums = IP.split("\\.");
        if (nums.length !=  4) {
            return false;
        }
        for (String x : nums) {
            // 0-255:
            if (x.length() == 0 || x.length() > 3) return false;
            // 0的情况
            if (x.charAt(0) == '0' && x.length() != 1) return false;
            // 大于255
            if (Integer.parseInt(x) > 255) return false;
        }
        return true;
    }
}