2016年7月21日星期四

[LeetCode] #93 Restore IP Addresses


public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(result, new ArrayList<String>(), s, 0);
        return result;
    }
    
    private void helper(List<String> result, List<String> path, String s, int start) {
        if (start == s.length()) {
            if (path.size() == 4) { //Attn!
                result.add(String.join(".", path));
            }
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            if (!isValid(s.substring(start, i + 1))) {
                break;
            }
            if (path.size() == 3 && i + 1 != s.length()) {
                continue;
            }
            path.add(s.substring(start, i + 1));
            helper(result, path, s, i + 1);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean isValid(String s) {
        if (s.length() != Integer.toString(Integer.parseInt(s)).length()) {
            return false; //Attn!
        }
        int i = Integer.parseInt(s);
        return (i >= 0 && i <= 255);
    }
}


没有评论:

发表评论