Java solution using DP


  • 0
    R

    Initialize the list array for 0 to n.
    if the string given is not enough then return empty list which is list[0].
    Then initialize list[1], which may have three options, x, xx, xxx. use the function split to validate the string.
    Then use the previous list[n-1] to create list[n] based on its current element.
    Last remove those elements which do not have the same length with given string s.
    Return the list.

    public List<String> restoreIpAddresses(String s) {
    		List<String>[] list = new ArrayList[5];
    		list[0] = new ArrayList<String>();
    		if(s.length()<4){
    			return list[0];
    		}
    		list[1] = new ArrayList<String>();
    		list[1].add(s.substring(0, 1));
    		if(split(s.substring(0, 2))){
    			list[1].add(s.substring(0, 2));
    		}
    		if(split(s.substring(0, 3))){
    			list[1].add(s.substring(0, 3));
    		}
            for(int i=1;i<4;i++){
        		list[i+1] = new ArrayList<String>();
            	for(String str:list[i]){
            		if(s.substring(str.length()-(i-1)).length()>=1)
    	        		list[i+1].add(str+"."+s.substring(str.length()-(i-1),str.length()-(i-1)+1));
            		if(s.substring(str.length()-(i-1)).length()>=2)
    	        		if(split(s.substring(str.length()-(i-1),str.length()-(i-1)+2))){
    	        			list[i+1].add(str+"."+s.substring(str.length()-(i-1),str.length()-(i-1)+2));
    	        		}
            		if(s.substring(str.length()-(i-1)).length()>=3)
    	        		if(split(s.substring(str.length()-(i-1),str.length()-(i-1)+3))){
    	        			list[i+1].add(str+"."+s.substring(str.length()-(i-1),str.length()-(i-1)+3));
    	        		}
            	}
            }
            List<String> l = new ArrayList<String>(list[4]);
            for(String str:list[4]){
            	if(str.length()-3!=s.length()){
            		l.remove(str);
            	}
            }
            return l;
        }
    	public boolean split(String s){
    		if(s.length()>1&&!s.startsWith("0")){
    			if(Integer.valueOf(s)<=255){
    				return true;
    			}
    		}
    		return false;
    	}

  • 0
    W

    I guess this is BFS. Not a real DP.


  • 0
    E

    I think so, this should be BFS


Log in to reply
 

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