Python solution sharing.


  • 0
    L

    This solution has some logic to check 0 started string. and use DFS to get the path.

    class Solution:
    # @param s, a string
    # @return a list of strings
    def restoreIpAddresses(self, s):
        def restoreIp(s,c,pathes,path):
            if(s==''):
                return;
            
            if(c==1):
                    if(s=='0' or ((256>int(s)>-1) and s[0]!='0')):
                        np=path+s;
                        pathes.append(np);
            else:
                minlen=min(3,len(s));
                
                if(s[0]=='0'):
                    np=path+s[0]+".";
                    restoreIp(s[1:],c-1,pathes,np);
                else:
                    for i in range(1,minlen):                    
                        np=path+s[0:i]+".";
                        restoreIp(s[i:],c-1,pathes,np);
    
                    if(len(s)>3 and 256>int(s[0:3])>-1):
                        np=path+s[0:3]+".";
                        restoreIp(s[3:],c-1,pathes,np);
    
        res=[];
        restoreIp(s,4,res,'');
        return res;

  • 0
    C

    Good job, Mast Qi. But recursion may cost n^2 time complexity. Is there a backtrack way to solve this problem? I like Python.

    1. Construct a solution space.
    2. Search the solution with backtrack way.
    3. Find all the solutions.

Log in to reply
 

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