【Leetcode】93. Restore IP Addresses

程序员文章站 2022-05-23 21:49:37

...

题目地址：

https://leetcode.com/problems/restore-ip-addresses/

将一个只含数字的字符串转化为合法的IP地址。合法的IP地址的格式是，由小数点"."分隔开的四个大于等于 $0$ 小于等于 $255$ 的整数，如果是正数则不能以 $0$ 开头。比如 $255.255.11.135$ ， $0.0.0.0$ 等等。

思路是用DFS暴搜。每次从某个位置出发，开始枚举当前新加入的那个大于等于 $0$ 小于等于 $255$ 的整数，其实也就是枚举从这个位置出发要分割原字符串多少个字符。只要满足条件，就进入下一层枚举，直到出发的位置已经到了字符串末尾（也就是到了递归树的叶子节点），就开始判断，如果已经切割出了四个数字，就说明当前的切割合法，加入res；否则直接return。代码如下：

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        
        dfs(s, 0, new StringBuilder(), 0, res);
        
        return res;
    }
    
    // 代表的是，从s的下标为pos的地方开始切割，sb是已经得到的字符串，cut代表已经切割出了多少段
    private void dfs(String s, int pos, StringBuilder sb, int cut, List<String> res) {
    	// 如果已经切割到末尾了，说明当前切割已经完成了，开始做判断
        if (pos == s.length()) {
        	// 如果此时切割的段数恰好是4，说明切割成功，将得到的字符串加入res
        	if (cut == 4) {
        		// 由于这里sb每次添加新的一段的时候，会在末尾加一个小数点，我们需要把这个小数点删掉，再加入res
            	res.add(sb.substring(0, sb.length() - 1));
            }
            // 否则说明切割的段数小于4，非法，直接返回
            return;
        }
        
    	// i表示当前切割片段的末尾。注意末尾可以到s的长度，因为s取substring的时候是包前不包后的
        for (int i = pos + 1; i <= s.length(); i++) {
        
        	// 开始从pos开始切长度为i - pos的一段
            String cur = s.substring(pos, i);
            
            // 如果当前的cur本身就是"0"或者不以"0"打头，并且cur代表的数字是小于等于255，
            // 并且当前切割出来的段数小于4，说明这个切割合法，可以尝试
            if ((!cur.startsWith("0") || "0".equals(cur)) 
            		&& Integer.parseInt(cur) <= 255 && cut < 4) {
            	// 那就把当前切割出来的这段数字append到当前字符串中去，并在结尾加个小数点
                sb.append(cur).append('.');
                
                // 进入下一次枚举。下一次枚举时，切割的起点就是i，切割段数加1
                dfs(s, i, sb, cut + 1, res);
                
                // 尝试完了之后，要恢复现场。把最后的小数点和cur清除掉
                sb.setLength(sb.length() - cur.length() - 1);
                
            } else if (cur.length() > 3) {  
            	// 如果当前切出来的长度都大于3了，再切更加不合法，直接剪枝，退出循环
                break;
            }
        }
    }
}

时间复杂度 $O(3^4)$ （实际上时间复杂度是常数量级的，因为递归树最多 $4$ 层，每层三个叉，所以整棵树的节点个数有个常数的上界），空间 $O(16)$ （是sb的最大可能长度，也就是四个三位数加上四个小数点。递归栈的深度是常数量级的，因为最多递归 $4$ 层）。