132. Palindrome Partitioning II

LeetCode hard original: C# #csharp #hard #leetcode #math #recursion #search #string

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

Дана cadena s. Разделите строку так, чтобы каждая substring разделения была палиндромом.

return минимальное количество разрезов, необходимых для разделения строки s на палиндромы.

Ejemplo:

Input: s = "aab"

Output: 1

Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

C# solución

coincidente/original

public class Solution {
    public int MinCut(string s) {
        return findMinimumCut(s, 0, s.Length - 1, s.Length - 1);
    }
    private int findMinimumCut(string s, int start, int end, int minimumCut) {
        if (start == end || isPalindrome(s, start, end)) {
            return 0;
        }
        for (int currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
            if (isPalindrome(s, start, currentEndIndex)) {
                minimumCut = Math.Min(
                    minimumCut, 1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut));
            }
        }
        return minimumCut;
    }
    private bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start++] != s[end--]) {
                return false;
            }
        }
        return true;
    }
}

C++ solución

borrador automático, revisar antes de enviar

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinCut(string s) {
        return findMinimumCut(s, 0, s.size() - 1, s.size() - 1);
    }
    private int findMinimumCut(string s, int start, int end, int minimumCut) {
        if (start == end || isPalindrome(s, start, end)) {
            return 0;
        }
        for (int currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
            if (isPalindrome(s, start, currentEndIndex)) {
                minimumCut = min(
                    minimumCut, 1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut));
            }
        }
        return minimumCut;
    }
    private bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start++] != s[end--]) {
                return false;
            }
        }
        return true;
    }
}

Java solución

coincidente/original

class Solution {
    public int minCut(String s) {
        return findMinimumCut(s, 0, s.length() - 1, s.length() - 1);
    }

    private int findMinimumCut(String s, int start, int end, int minimumCut) {
        if (start == end || isPalindrome(s, start, end)) {
            return 0;
        }

        for (int currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
            if (isPalindrome(s, start, currentEndIndex)) {
                minimumCut = Math.min(
                    minimumCut,
                    1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut)
                );
            }
        }
        return minimumCut;
    }

    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}

JavaScript solución

coincidente/original

var minCut = function (s) {
    return findMinimumCut(s, 0, s.length - 1, s.length - 1);
};

var findMinimumCut = function (s, start, end, minimumCut) {
    if (start === end || isPalindrome(s, start, end)) {
        return 0;
    }
    for (let currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
        if (isPalindrome(s, start, currentEndIndex)) {
            minimumCut = Math.min(
                minimumCut,
                1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut),
            );
        }
    }
    return minimumCut;
};

var isPalindrome = function (s, start, end) {
    while (start < end) {
        if (s[start++] !== s[end--]) {
            return false;
        }
    }
    return true;
};

Python solución

coincidente/original

class Solution:
    def minCut(self, s: str) -> int:
        return self.findMinimumCut(s, 0, len(s) - 1, len(s) - 1)

    def findMinimumCut(self, s: str, start: int, end: int, minimumCut: int) -> int:
        if start == end or self.isPalindrome(s, start, end):
            return 0
        for currentEndIndex in range(start, end + 1):
            if self.isPalindrome(s, start, currentEndIndex):
                minimumCut = min(
                    minimumCut,
                    1 + self.findMinimumCut(s, currentEndIndex + 1, end, minimumCut)
                )
        return minimumCut

    def isPalindrome(self, s: str, start: int, end: int) -> bool:
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

Go solución

coincidente/original

func minCut(s string) int {
    return findMinimumCut(s, 0, len(s)-1, len(s)-1)
}

func findMinimumCut(s string, start int, end int, minimumCut int) int {
    if start == end || isPalindrome(s, start, end) {
        return 0
    }
    for currentEndIndex := start; currentEndIndex <= end; currentEndIndex++ {
        if isPalindrome(s, start, currentEndIndex) {
            minimumCut = min(
                minimumCut,
                1+findMinimumCut(s, currentEndIndex+1, end, minimumCut),
            )
        }
    }
    return minimumCut
}

func isPalindrome(s string, start int, end int) bool {
    for start < end {
        if s[start] != s[end] {
            return false
        }
        start++
        end--
    }
    return true
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

1️⃣

Definición задачи и начальные условия:

Algoritmo обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end.

Чтобы find минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut.

Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом).

2️⃣

Генерация подстрок и рекурсивный поиск:

Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки.

3️⃣

Enunciado палиндрома и рекурсивное разделение:

Если текущая substring является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем minimum разрез для оставшейся строки

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.