132. Palindrome Partitioning II

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

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

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

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

Esempio:

Input: s = "aab"

Output: 1

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

C# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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️⃣

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

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

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

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

2️⃣

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

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

3️⃣

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.