93 Restore IP Addresses

Java

使用类变量方式存储Restore过程中产生的答案，存储在output中，将过程中的分段存储在segments中，使用valid()函数检验每个分段的部分是否满足IP地址段的要求。使用update_output函数进行更新结果。backtrack()函数使用回溯的思想进行处理。

class Solution {
    int n;
    String s;
    LinkedList<String> segments = new LinkedList<String>();
    ArrayList<String> output = new ArrayList<String>();

    public boolean valid(String segment){
        int m = segment.length();
        if(m > 3)
            return false;
        return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255): (m == 1);
    }

    public void update_output(int curr_pos){

        String segment = s.substring(curr_pos + 1, n);
        if (valid(segment)){
            segments.add(segment);
            output.add(String.join(".",  segments));
            segments.removeLast();
        }
    }
    private void backtrack(int prev_pos, int dots){
        int max_pos = Math.min(n - 1, prev_pos + 4);
        for(int curr_pos = prev_pos + 1; curr_pos < max_pos; curr_pos ++){
            String segment = s.substring(prev_pos + 1, curr_pos + 1);
            if(valid(segment)){
                segments.add(segment);
                if(dots - 1 == 0)
                    update_output(curr_pos);
                else
                    backtrack(curr_pos, dots - 1);
                segments.removeLast();
            }
        }

    }
    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        this.s = s;
        backtrack(-1, 3);
        return output;
    }
}