Skip to content

93. Restore IP Addresses 👍

  • Time: $O(3^4)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  vector<string> restoreIpAddresses(const string& s) {
    vector<string> ans;
    dfs(s, 0, {}, ans);
    return ans;
  }

 private:
  void dfs(const string& s, int start, vector<string>&& path,
           vector<string>& ans) {
    if (path.size() == 4 && start == s.length()) {
      ans.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
      return;
    }
    if (path.size() == 4 || start == s.length())
      return;

    for (int length = 1; length <= 3; ++length) {
      if (start + length > s.length())
        return;  // out-of-bounds
      if (length > 1 && s[start] == '0')
        return;  // leading '0'
      const string& num = s.substr(start, length);
      if (stoi(num) > 255)
        return;
      path.push_back(num);
      dfs(s, start + length, std::move(path), ans);
      path.pop_back();
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public List<String> restoreIpAddresses(final String s) {
    List<String> ans = new ArrayList<>();
    dfs(s, 0, new ArrayList<>(), ans);
    return ans;
  }

  private void dfs(final String s, int start, List<String> path, List<String> ans) {
    if (path.size() == 4 && start == s.length()) {
      ans.add(String.join(".", path));
      return;
    }
    if (path.size() == 4 || start == s.length())
      return;

    for (int length = 1; length <= 3; ++length) {
      if (start + length > s.length()) // out-of-bounds
        return;
      if (length > 1 && s.charAt(start) == '0') // leading '0'
        return;
      final String num = s.substring(start, start + length);
      if (Integer.parseInt(num) > 255)
        return;
      path.add(num);
      dfs(s, start + length, path, ans);
      path.remove(path.size() - 1);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def restoreIpAddresses(self, s: str) -> list[str]:
    ans = []

    def dfs(start: int, path: list[int]) -> None:
      if len(path) == 4 and start == len(s):
        ans.append(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3])
        return
      if len(path) == 4 or start == len(s):
        return

      for length in range(1, 4):
        if start + length > len(s):
          return  # out-of-bounds
        if length > 1 and s[start] == '0':
          return  # leading '0'
        num = s[start: start + length]
        if int(num) > 255:
          return
        dfs(start + length, path + [num])

    dfs(0, [])
    return ans