My simple Java solution, how to analysis the time complexity?


  • 0
    Y

    public List<String> restoreIpAddresses(String s) {

    	List<String> result = new ArrayList<String>();
    	if(s.length() < 4 || s.length() > 12)
    		return result;
    	String temp1, temp2, temp3;
    	int t = 0;
    	for(int i=1; i<=3 && i<=s.length()-3; i++) {
    		temp1 = "";
    		if(i>1 && s.charAt(0)=='0')
    			continue;
    		if(Integer.parseInt(s.substring(0, i)) > 255)
    			break;
    		temp1 = s.substring(0, i) + ".";
    		for(int j=i+1; j<=i+4 && j<=s.length()-2; j++) {
    			temp2 = temp1;
    			t = Integer.parseInt(s.substring(i, j));
    			if(t>255 || (j>i+1 && s.charAt(i)=='0'))
    				break;
    			temp2 += s.substring(i, j) + ".";
    			for(int m=j+1; m<=j+4 && m<=s.length()-1; m++) {
    				temp3 = temp2;
    				t = Integer.parseInt(s.substring(j, m));
    				if((t>255) || (m>j+1 && s.charAt(j)=='0'))
    					break;
    				temp3 += s.substring(j, m) + ".";
    				t = Integer.parseInt(s.substring(m));
    				if(t>255 || m<s.length()-1 && s.charAt(m)=='0')
    					continue;
    				result.add(temp3 + s.substring(m));
    			}
    		}
    	}
    	return result;
    }

  • 0
    J

    Here is my answer, welcome your suggestions for improvement.

    public List<String> restoreIpAddress(String ip) {
            List<List<String>> result = new LinkedList<>();
            List<String> output = new LinkedList<>();
    
            List<String> list = new LinkedList<>();
            helper(ip, 0, list, result);
            // convert list to a string
            for(List<String>  ipStrings : result) {
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i< ipStrings.size(); i++) {
                    sb.append(ipStrings.get(i));
                    if (i != ipStrings.size()-1) {
                        sb.append(".");
                    }
                }
                output.add(sb.toString());
            }
            return output;
        }
    
        private void helper(String ip, int start, List<String> list, List<List<String>> result) {
            if (list.size() >=4 && start < ip.length()) {
                return;
            }
            if (list.size() == 4 && start == ip.length()) {
                List<String>  newList = new LinkedList<>();
                newList.addAll(list);
                result.add(newList);
                return;
            }
            if (start <= ip.length()-3) {
                String sub3 = ip.substring(start, start+3);
                if (sub3.charAt(0) != '0' && Integer.parseInt(sub3) <= 255) {
                    list.add(sub3);
                    helper(ip, start+3, list, result);
                    list.remove(list.size()-1);
                }
            }
            if (start <= ip.length()-2) {
                String sub2 = ip.substring(start, start+2);
                if (sub2.charAt(0) != '0') {
                    list.add(sub2);
                    helper(ip, start + 2, list, result);
                    list.remove(list.size() - 1);
                }
            }
            if (start <= ip.length()-1) {
                String sub1 = ip.substring(start, start + 1);
                list.add(sub1);
                helper(ip, start + 1, list, result);
                list.remove(list.size()-1);
            }
        }
    
        public static void main(String[] args) {
            RestoreIPAddress restoreIPAddress = new RestoreIPAddress();
            System.out.println(restoreIPAddress.restoreIpAddress("25525511135"));
            System.out.println(restoreIPAddress.restoreIpAddress("010010"));
    
        }

Log in to reply
 

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