title: Building IP addresses from string
body: <blockquote>
    <p>Write a program that determines where to add periods to a decimal string so that the resulting string is a valid IP address. There may be more than one valid IP address corresponding to a string, in which case you should print all possibilities. For example, <code>"19216811"</code>, two of the nine possible IP addresses include <code>192.169.1.1</code> and <code>19.216.81.1</code>.</p>
  </blockquote>
  
  <p>Below is my (incomplete) solution:</p>
  
  <pre><code>def valid_ips(string):
    def is_valid_part(part):
      return len(part) == 1 or (part[0] != 0 and int(part) &lt;= 255)  
  
    def build_valid_ips(substring):
      result = []
      for i in range(1, min(4, len(substring))):
        part = substring[:i]
        if is_valid_part(part):
          for sub in build_valid_ips(substring[i:]):
            result.append(part + '.' + sub)
      return result
  
    return build_valid_ips(string)
  </code></pre>
  
  <p>This is a variant problem in the book I'm working out of, so I don't have a solution to look at. However, I have a couple of questions</p>
  
  <ul>
  <li>This solution is incorrect, as it always returns an empty list but I'm not sure why. Seems like I'm handling the inductive step and base case just fine. Could someone point me in the right direction?</li>
  <li>How can I do this better? I understand each recursive call generates a new list and multiple new strings which adds a ton of overhead, but how to avoid this?</li>
  </ul>