93. Restore IP Addresses.md

93. Restore IP Addresses

---

leetcode-cn Daily Challenge on August 9th, 2020.

---

Difficulty : Medium

Related Topics : String、Backtracking

---

Given a string s containing only digits. Return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single points and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "1111"
Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"
Output: ["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

• 0 <= s.length <= 3000
• s consists of digits only.

---

Solution

• mine
  • Java
    • DFS Runtime: 5 ms, faster than 63.45%, Memory Usage: 39.7 MB, less than 65.39% of Java online submissions

      public List<String> restoreIpAddresses(String s) {
          List<String> res = new LinkedList<>();
          dfs(s, res, 0, 0, "");
          return res;
      }
      
      void dfs(String s, List<String> list, int start, int index, String res) {
          int m = 4 - index;
          if (start + m > s.length() || start + 3 * m < s.length() || m <= 0) return;
      
          if (index == 3) {
              String item = s.substring(start);
              if (Integer.parseInt(item) > 255) return;
              if(s.charAt(start) == '0' && start + 1 != s.length()) return;
              item = res + "." + item;
              list.add(item);
              return;
          }
      
          for (int i = start + 1; i < s.length() && i <= start + 3; i++) {
              String item = s.substring(start, i);
              if (Integer.parseInt(item) > 255) continue;
              String t = res.length() == 0 ? item : res + "." + item;
              dfs(s, list, i, index + 1, t);
      
              if(s.charAt(start) == '0') break;
          }
      }
      

---

• the most votes

• Runtime: 8 ms, faster than 35.28%，Memory Usage: 40.1 MB, less than 35.33% of Java online submissions

  public List<String> restoreIpAddresses(String s) {
      List<String> res = new ArrayList<String>();
      int len = s.length();
      for (int i = 1; i < 4 && i < len - 2; i++) {
          for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
              for (int k = j + 1; k < j + 4 && k < len; k++) {
                  String s1 = s.substring(0, i), s2 = s.substring(i, j), s3 = s.substring(j, k), s4 = s.substring(k, len);
                  if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                      res.add(s1 + "." + s2 + "." + s3 + "." + s4);
                  }
              }
          }
      }
      return res;
  }
  
  public boolean isValid(String s) {
      return s.length() <= 3 && s.length() != 0 && (s.charAt(0) != '0' || s.length() <= 1) && Integer.parseInt(s) <= 255;
  }
  

---