例题

lc 93. 复原IP地址

思路

• 递归
• 三指针

代码
Python代码：

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        seg_count = 4
        ans = []
        segments = [0] * seg_count
        def dfs(segId, start):
            if segId == seg_count:
                if start == len(s):
                    ip = ".".join(str(s) for s in segments)
                    ans.append(ip)
                return
            if start == len(s):
                return
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[start] == "0":
                segments[segId] = 0
                dfs(segId + 1, start + 1)
            addr = 0
            for end in range(start, len(s)):
                addr = addr * 10 + (ord(s[end]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, end + 1)
                else:
                    break
        dfs(0, 0)
        return ans

Java三指针：

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> r = new ArrayList<>();
        if(s.length() > 12) return r;
        for(int i = 1; i < s.length() && i <= 3; ++i){
            for(int j = i; j < s.length() && j <= i + 3; ++j){
                for(int k = j; k < s.length() && k <= j + 3; ++k){
                    String s1 = s.substring(0, i);
                    String s2 = s.substring(i, j);
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k);
                    if(f(s1)&&f(s2)&&f(s3)&&f(s4)){
                        StringBuilder sb = new StringBuilder();
                        sb.append(s1); sb.append(".");
                        sb.append(s2); sb.append(".");
                        sb.append(s3); sb.append(".");
                        sb.append(s4);
                        r.add(sb.toString());
                    }
                }
            }
        }
        return r;
    }
    boolean f(String s){
        if(s.length() == 0) return false;
        if(s.length() == 1) return true;
        if(s.length() > 3) return false;
        if(s.charAt(0) == '0') return false;
        if(Integer.parseInt(s) <= 255) return true;
        return false;
    }
}