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

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length() < 4)
            return res;

        helper(res, new StringBuilder(), 0, 0, s);
        return res;
    }

    public void helper(List<String> res, StringBuilder sb, int count, int start, String s) {
        if(start == s.length()) {
            if(count == 4) {
                res.add(sb.substring(0, sb.length() - 1));
            }
            return;
        }

        if(count == 4)
            return;

        for(int i = start + 1; i <= s.length(); i++) {
            String part = s.substring(start, i);
            if(isValid(part)) {
                int len = sb.length();
                sb.append(part).append('.');
                helper(res, sb, count + 1, i, s);
                sb.setLength(len);
            } else {
                return;
            }
        }
    }

    public boolean isValid(String s) {
        if(s == null || s.length() == 0)
            return false;
        if(s.charAt(0) == '0' && s.length() > 1)
            return false;
        int n = Integer.parseInt(s);
        return n >= 0 && n <= 255;
    }
}