Share my Java solution


  • 1
    P
    public List<String> restoreIpAddresses(String s) {
            return recursion(s, 0, 1, "");
        }
        
        private List<String> recursion(String s, int index, int num, String tempIP) {
            List<String> res = new ArrayList<String>();
            if(num == 4) {
                if(checkNum(s, index, s.length()))
                    res.add(tempIP + s.substring(index, s.length()));
                return res;
            }
            for(int i = 1; i < 4; i++) {
                if(checkNum(s, index, index + i)) {
                    String temp = tempIP + s.substring(index, index + i) + ".";
                    res.addAll(recursion(s, index + i, num + 1, temp));
                }
            }
            
            return res;
        }
        
        private boolean checkNum(String s, int start, int end) {
            if(end > s.length() || start >= s.length() || end - start > 3)
                return false;
            if(s.charAt(start) == '0' && end - start > 1)
                return false;
            if(Integer.valueOf(s.substring(start, end)) < 256)
                return true;
            return false;
        }

  • 0
    L

    public class Solution {

    public List<String> restoreIpAddresses(String s) {
    	if(s.equals(null))
    		return null;
    	if(s.trim().length() == 0)
    	    return new ArrayList<String>();
    	List<String> ret = new ArrayList<String>();
    	helper(ret, "", s, 4);
    	return ret;
    }
    
    public boolean helper(List<String> store, String ip, String s, int number) {
    
    	if(s.length() > 3 * number)
    		return false;
    	if(s.length() < number)
    		return false;
    	if(number == 0) {
    	   store.add(ip.substring(0, ip.length() - 1));
    	   return true;
    	}
    
    	if(s.substring(0, 1).equals("0")) {
    		return helper(store, ip + "0.", s.substring(1, s.length()), number - 1);
    	} else {
    		boolean bol = false;
    		for(int i = 1; i <= (s.length() < 3 ? s.length() : 3); i++) {
    			if(i == 3)
    				bol = (Integer.valueOf(s.substring(0, 3)) <= 255 && helper(store, ip + s.substring(0, 3) + ".", s.substring(3, s.length()), number - 1)) || bol;
    			else
    				bol = helper(store, ip + s.substring(0, i) + ".", s.substring(i, s.length()), number - 1) || bol;
    		}
    		return bol;
    	}
    }
    

    }


Log in to reply
 

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