Java clean and short solution using back tracing


  • 1
    S

    public class Solution {
    public List<String> restoreIpAddresses(String s) {
    return helper(s, 0);
    }

    public boolean isValid(String s) {
        if (s.length() > 3 || s.length() == 0)
            return false;
        if (s.length() > 1 && s.charAt(0) == '0')
            return false;
        if (s.length() == 3 && Integer.parseInt(s) > 255)
            return false;
        return true;
    }
    
    public List<String> helper(String s, int idx) {
        List<String> ret = new ArrayList<String>();
        if (idx == 3) {
            if (isValid(s)) {
                ret.add(s);
            }
            return ret;
        }
        int len = s.length();
        for (int i = 1; i <= 3; ++i) {
            if (i <= len) {
                String a = s.substring(0, i);
                if (!isValid(a)) 
                    continue;
                List<String> l1 = helper(s.substring(i), idx + 1);
                for (String str: l1) {
                    ret.add(a + "." + str);
                }
            }
        }
        return ret;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.