public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ret = new LinkedList<String>();
        dfs(ret, s, "", 0 ,0);
        return ret;
    }
    public void dfs(List<String> ret, String s, String sol, int index, int len){
        if (index == s.length() && len == 4){
            ret.add(sol);
            return;
        }
        if (len == 4 || index > s.length())
            return;

        for (int l = 1; l<4; l++){
            if(index+l > s.length())
                return;
            String sub = s.substring(index, index+l);
            if ((sub.startsWith("0") && sub.length()>1) || (l==3 && Integer.parseInt(sub)>=256))
                continue;
            dfs(ret, s, sol+sub+(len==3?"":"."), index+l, len+1);
        }
    }
}

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """

        ret = []
        if not s:
            return ret

        self.findIP(s,ret,"",0)
        return ret

    def findIP(self,s,ret,tmp,r):
        if r == 4:
            if not s:
                ret.append(tmp[:len(tmp)-1])
            return


        for i in range(1,4):
            # 这里是等号，否则当s只有一个字符的时候,就不执行下面代码了
            if i <= len(s):
                ip = s[:i]
                if int(ip) <= 255:
                    self.findIP(s[i:],ret,tmp+ip+".",r+1)
                # make sure "00" "01" will not happen
                if s[0] == "0":
                    break
        return
if __name__ == "__main__":
    sol = Solution()
    sol.restoreIpAddresses("0000")