Восстановление IP-адреса в Kotlin

Этот пост посвящен решению на Kotlin для поиска всех действительных IP-адресов, которые могут быть сформированы путем вставки точек в заданную строку цифр. Решение использует комбинацию вложенных циклов и вспомогательной функции для проверки достоверности частей IP-адреса. Кроме того, он обеспечивает анализ временной и пространственной сложности решения.

Временная сложность решения составляет O(1), а пространственная сложность составляет O(n), где n — длина входной строки.

Вот пример решения в Kotlin для поиска всех действительных IP-адресов, которые могут быть образованы путем вставки точек в заданную строку цифр:

Эта функция принимает строку s цифр в качестве входных данных и возвращает список всех действительных IP-адресов, которые могут быть сформированы путем вставки точек в строку. п

Он использует три вложенных цикла для создания всех возможных комбинаций позиций для вставки точек в строку.

n Для каждой комбинации он делит строку на четыре части, используя метод подстроки, и проверяет, является ли каждая часть допустимым целым числом от 0 до 255, используя вспомогательную функцию isValid. n Если все четыре части допустимы, они объединяются точками для формирования действительного IP-адреса и добавляются в список результатов. п

Вспомогательная функция isValid проверяет, длиннее ли строка, чем 3 символа, начинается ли она с 0, является ли она пустой или больше 255, и возвращает false, если какое-либо из условий истинно, в противном случае она возвращает true. .

:::информация Важно отметить, что этот алгоритм представляет собой решение методом грубой силы, которое генерирует все возможные комбинации позиций для вставки точек и проверки того, являются ли они допустимыми IP-адресами. Это может потребовать значительных вычислительных ресурсов для больших входных данных.

:::

n Временная сложность этого решения равна O(1), поскольку решение генерирует все возможные комбинации позиций для вставки точек в строку.

n Для каждой комбинации он делит строку на четыре части и проверяет, является ли каждая часть допустимым целым числом от 0 до 255, используя вспомогательную функцию isValid.

n Наихудший сценарий состоит в том, что строка имеет длину 12 цифр, в этом случае решение сгенерирует 3^4 = 81 комбинацию и для каждой комбинации проверит правильность 4 частей. n Таким образом, общая временная сложность решения составляет O(3^4 * 4), т.е. O(81*4), т.е. O(324), т.е. O(1)

n Объемная сложность этого решения равна O(n), где n — длина входной строки. n Решение использует список для хранения действительных IP-адресов и несколько переменных для хранения промежуточных результатов, таких как currMax, currMin, totalSum и количество. Эти переменные занимают O(1) места.

n Решение также использует рекурсию для реализации поиска в глубину, где он может вызывать себя несколько раз. Это приводит к созданию стека вызовов, занимающего O(n) места в худшем случае, когда вся входная строка состоит из единиц.

n В этом случае решение вызывает функцию dfs рекурсивно для каждой «1» во входной строке, и оно может вызывать функцию dfs до n раз, где каждый вызов занимает O (1) пространство, что приводит к O (n) пространственная сложность.

Как правило, объемная сложность этого решения составляет O(n), где n – длина входной строки, так как необходимо хранить выходной список и использовать стек вызовов для рекурсивных вызовов.

:::информация Важно отметить, что сложность пространства прямо пропорциональна размеру входных данных, и в данном случае она линейна по отношению к размеру входной строки.

:::

Код

fun restoreIpAddresses(s: String): List<String> {
    val result = arrayListOf<String>()
    for (i in 0..3) {
        for (j in i + 1..i + 3) {
            for (k in j + 1..j + 3) {
                if (i < s.length && j < s.length && k < s.length) {
                    val s1 = s.substring(0, i)
                    val s2 = s.substring(i, j)
                    val s3 = s.substring(j, k)
                    val s4 = s.substring(k, s.length)
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                        result.add("$s1.$s2.$s3.$s4")
                    }
                }
            }
        }
    }
    return result
}

fun isValid(s: String): Boolean {
    if (s.length > 3 || s.isEmpty() || s[0] == '0' && s.length > 1 || s.toInt() > 255) return false
    return true
  }
}

n Надеюсь, это поможет! Дайте мне знать, если у вас есть другие вопросы в комментариях.