Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"Output: ["255.255.11.135", "255.255.111.35"]

难度：medium

题目：给定一字符串仅包含数字，恢复该字符串为所有可能合法的IP地址组合。

思路：递归

Runtime: 2 ms, faster than 91.11% of Java online submissions for Restore IP Addresses.

class Solution {    public List
    
      restoreIpAddresses(String s) {        List
     
       result = new ArrayList();        if (null == s || s.length() < 4 || s.length() > 12) {            return result;        }                restoreIpAddresses(s, 0, 0, "", result);                return result;    }        private void restoreIpAddresses(String s, int i, int cnt, String str, List
      
        result) {        int sLength = s.length();        if (i >= sLength && cnt >= 4) {            result.add(str.substring(0, str.length() - 1));            return;        }                int i1 = (i + 1) <= sLength ? Integer.parseInt(s.substring(i, i + 1)) : -1;        if (i1 >= 0 && cnt < 4) {            restoreIpAddresses(s, i + 1, cnt + 1, str + i1 + ".", result);        }        int i2 = (i + 2) <= sLength ? Integer.parseInt(s.substring(i, i + 2)) : -1;        if (i2 >= 10 && i2 <= 99 && cnt < 4) {            restoreIpAddresses(s, i + 2, cnt + 1, str + i2 + ".", result);        }                int i3 = (i + 3) <= sLength ? Integer.parseInt(s.substring(i, i + 3)) : -1;        if (i3 >= 100 && i3 <= 255 && cnt < 4) {            restoreIpAddresses(s, i + 3, cnt + 1, str + i3 + ".", result);        }    }}