关于java:LeetCode093复原-IP-地址

26次阅读

共计 1634 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：给定一个只蕴含数字的字符串，用以示意一个 IP 地址，返回所有可能从 s 取得的无效 IP 地址。你能够按任何程序返回答案。

无效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201″ 和 “192.168.1.1” 是无效 IP 地址，然而 “0.011.255.245”、”192.168.1.312″ 和 “192.168@1.1” 是有效 IP 地址。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：回溯算法

IP 地址分为 4 段，记录每一段的 IP 地址的值，而后从第一段开始解决，递归进行判断前面的 IP 地址是否符合条件。

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

public class LeetCode_093 {
    // IP 地址一共有 4 段
    private static final int SEG_COUNT = 4;
    // IP 地址 4 段的值别离是多少
    private static int[] segments;
    // 后果集
    private static List<String> result = new ArrayList<>();

    public static List<String> restoreIpAddresses(String s) {segments = new int[SEG_COUNT];
        dfs(s, 0, 0);
        return result;
    }

    /**
     * 回溯算法
     *
     * @param s        原始字符串
     * @param segId    以后是第几段 IP 地址
     * @param segStart 以后第 segId 段 IP 地址的起始地位
     */
    private static void dfs(String s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，则阐明以后后果是一种符合条件的 IP 地址
        if (segId == SEG_COUNT) {if (segStart == s.length()) {StringBuffer ipAddr = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; ++i) {ipAddr.append(segments[i]);
                    if (i != SEG_COUNT - 1) {ipAddr.append('.');
                    }
                }
                result.add(ipAddr.toString());
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址，字符串就曾经遍历完了，则提前退出
        if (segStart == s.length()) {return;}

        // 因为不能有前导 0，如果以后数字为 0，那么这一段 IP 地址只能是 0
        if (s.charAt(segStart) == '0') {segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        // 个别状况下，每一种可能都要思考
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {break;}
        }
    }

    public static void main(String[] args) {for (String restoreIpAddress : restoreIpAddresses("101023")) {System.out.println(restoreIpAddress);
        }
    }
}