Leetcode93. 复原IP地址

一个会写诗的程序员

修改于 2023-09-21 17:07:07

59900

代码可运行

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

运行总次数：0

代码可运行

题目描述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

93. Restore IP Addresses

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

Example:

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

解题思路

IP的格式分析:

seg1.seg2.seg3.seg4

seg都是1-3位数字; 然后 seg1+seg2+seg3+seg4 = 字符串的长度.

源代码

fun restoreIpAddresses(s: String): List<String> {
    val result = mutableListOf<String>()
    val ip = StringBuilder()

    for (seg1 in 1..3) {
        for (seg2 in 1..3) {
            for (seg3 in 1..3) {
                for (seg4 in 1..3) {

                    if (seg1 + seg2 + seg3 + seg4 == s.length) {

                        val v1 = s.substring(0, seg1).toInt()
                        val v2 = s.substring(seg1, seg1 + seg2).toInt()
                        val v3 = s.substring(seg1 + seg2, seg1 + seg2 + seg3).toInt()
                        val v4 = s.substring(seg1 + seg2 + seg3).toInt()

                        if (v1 <= 255 && v2 <= 255 && v3 <= 255 && v4 <= 255) {
                            ip.append(v1).append(".")
                                .append(v2).append(".")
                                .append(v3).append(".")
                                .append(v4)

                            val sip = ip.toString()
                            if (sip.length == s.length + 3) {
                                result.add(sip)
                            }
                            // clear StringBuilder, ready to next for loop use
                            ip.clear()
                        }
                    }

                }
            }
        }
    }
    return result
}

fun main() {
    val s = "25525511135"
    val ans = restoreIpAddresses(s)
    println(ans) // [255.255.11.135, 255.255.111.35]
}