🌕 93. 复原 IP 地址

难度: 🌕

问题描述

---

解法

class Solution {
    List<String> res = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        // 思路:
        // 分割字符串 s 使其分成 4 份 && 每份都满足 ip 条件
        int len = s.length();
        LinkedList<Integer> path = new LinkedList<>();
        mySol(s, len, 0, path);
        return res;
    }

    private void mySol(String s, int len, int index, LinkedList<Integer> path) {
        // 递归终止条件
        if(index == len) {
            if(path.size() == 4) {
                res.add(getStr(path));
            }
            return;
        }
        if(path.size() >= 4) {
            return;
        }
        // index < len && size() < 4
        for(int i = index; i < Math.min(len, index + 3); i ++) {
            String str = s.substring(index, i + 1);
            int cur = Integer.valueOf(str);
            // 除去前导0
            if(str.charAt(0) == '0' && str.length() > 1) {
                return;
            }
            if(cur > 255) {
                return;
            }
            path.addLast(cur);
            mySol(s, len, i + 1, path);
            path.removeLast();
        }
    }

    private String getStr(LinkedList<Integer> path) {
        StringBuilder sb = new StringBuilder();
        int len = path.size();
        for(int i = 0; i < len - 1; i ++) {
            sb.append(path.get(i)).append(".");
        }
        sb.append(path.get(len - 1));
        return sb.toString();
    }
}

---

输出