首页 > 代码库 > 【leetcode刷题笔记】Restore IP Addresses

【leetcode刷题笔记】Restore IP Addresses

2024-07-14 00:32:05   215人阅读

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

 

题解：深度优先搜索。用result存放得到的每个小数点之间的字符串，在递归函数 private void restoreIpRecur(String s,List<String> answer,ArrayList<String> result){ 中每次从s的头取1个，2个和3个（如果能取到，注意边界判断）组成一个数字，如果该数字在0~255之间（且不是00)，就存入result中备用，然后递归的在s剩下的子串里面搜索后面的数字。

递归终止条件：

  • result列表中有四个数字，并且s正好变成空串，说明result中存放的4个数字可以组成一组ip地址，把它存入answer中；
  • result列表中有大于或者等于4个数字，但s不为空，说明将s分成了4段以上，不符合规则，return。

代码如下：

 1 public class Solution { 2     private boolean isValidIp(String ip){ 3         if(ip.charAt(0) == ‘0‘) 4             return ip.equals("0"); 5         int digit = Integer.valueOf(ip); 6         return digit >= 0 && digit <= 255; 7     } 8     private void restoreIpRecur(String s,List<String> answer,ArrayList<String> result){ 9         //result has more than four numbers but s is not empty, means we sperate s to more than 4 numbers10         if(result.size()>=4 && !s.isEmpty())11             return;12         if(s.equals("")){13             //if we sperate s exactly four valid numbers14             if(result.size()==4){15                 //found one IP16                 String ip = new String();17                 for(String ss:result)18                     ip = ip + ss + ".";19                 ip = ip.substring(0,ip.length()-1);20                 answer.add(ip);21             }22             else {23                 return;24             }25         }26         //get 1,2,3 characters from s‘s head and put it into result,search what‘s left in s recursively27         for(int i = 1;i<=3&&i<=s.length();i++){28             String sub = s.substring(0,i);29             if(isValidIp(sub)){30                 result.add(sub);31                 restoreIpRecur(s.substring(i), answer, result);32                 result.remove(result.size()-1);33             }34         }35         return;36     }37     public List<String> restoreIpAddresses(String s) {38         ArrayList<String> answer = new ArrayList<String>();39         ArrayList<String> result = new ArrayList<String>();40         restoreIpRecur(s, answer, result);41         return answer;42         43     }44 }


联系
我们