1278. Palindrome Partitioning III

LeetCode hard original: C# #csharp #dynamic-programming #hard #leetcode #math #string

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

LeetCode Static

Вам дана stringa s, содержащая строчные буквы, и intero k. Вам нужно: Сначала заменить некоторые символы s на другие строчные английские буквы. Затем разделить s на k непустых непересекающихся подстрок так, чтобы каждая substring была палиндромом. return минимальное количество символов, которое нужно изменить, чтобы разделить строку.

Esempio:

Input: s = "abc", k = 2

Output: 1

C# soluzione

abbinato/originale

public class Solution {
    public int MinChangesToMakePalindrome(string s, int k) {
        int n = s.Length;
        
        int MinChangeToPalindrome(string s, int i, int j) {
            int changes = 0;
            while (i < j) {
                if (s[i] != s[j]) {
                    changes++;
                }
                i++;
                j--;
            }
            return changes;
        }
        int[,] dp1 = new int[n, n];
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp1[i, j] = MinChangeToPalindrome(s, i, j);
            }
        }
        int[,] dp2 = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp2[i, j] = int.MaxValue;
            }
        }
        dp2[0, 0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int kk = 1; kk <= k; kk++) {
                for (int j = 0; j < i; j++) {
                    dp2[i, kk] = Math.Min(dp2[i, kk], dp2[j, kk - 1] + dp1[j, i - 1]);
                }
            }
        }
        return dp2[n, k];
    }
}

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 MinChangesToMakePalindrome(string s, int k) {
        int n = s.size();
        
        int MinChangeToPalindrome(string s, int i, int j) {
            int changes = 0;
            while (i < j) {
                if (s[i] != s[j]) {
                    changes++;
                }
                i++;
                j--;
            }
            return changes;
        }
        int[,] dp1 = new int[n, n];
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp1[i, j] = MinChangeToPalindrome(s, i, j);
            }
        }
        int[,] dp2 = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp2[i, j] = int.MaxValue;
            }
        }
        dp2[0, 0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int kk = 1; kk <= k; kk++) {
                for (int j = 0; j < i; j++) {
                    dp2[i, kk] = min(dp2[i, kk], dp2[j, kk - 1] + dp1[j, i - 1]);
                }
            }
        }
        return dp2[n, k];
    }
}

Java soluzione

abbinato/originale

public class Solution {
    public int minChangesToMakePalindrome(String s, int k) {
        int n = s.length();
        
        int[][] dp1 = new int[n][n];
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp1[i][j] = minChangeToPalindrome(s, i, j);
            }
        }

        int[][] dp2 = new int[n + 1][k + 1];
        for (int[] row : dp2) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp2[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int kk = 1; kk <= k; kk++) {
                for (int j = 0; j < i; j++) {
                    dp2[i][kk] = Math.min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1]);
                }
            }
        }

        return dp2[n][k];
    }

    private int minChangeToPalindrome(String s, int i, int j) {
        int changes = 0;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                changes++;
            }
            i++;
            j--;
        }
        return changes;
    }
}

Go soluzione

abbinato/originale

import (
    "math"
)

func minChangesToMakePalindrome(s string, k int) int {
    n := len(s)
    
    minChangeToPalindrome := func(s string, i, j int) int {
        changes := 0
        for i < j {
            if s[i] != s[j] {
                changes++
            }
            i++
            j--
        }
        return changes
    }

    dp1 := make([][]int, n)
    for i := range dp1 {
        dp1[i] = make([]int, n)
    }
    for length := 1; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            dp1[i][j] = minChangeToPalindrome(s, i, j)
        }
    }

    dp2 := make([][]int, n+1)
    for i := range dp2 {
        dp2[i] = make([]int, k+1)
        for j := range dp2[i] {
            dp2[i][j] = math.MaxInt32
        }
    }
    dp2[0][0] = 0

    for i := 1; i <= n; i++ {
        for kk := 1; kk <= k; kk++ {
            for j := 0; j < i; j++ {
                dp2[i][kk] = min(dp2[i][kk], dp2[j][kk-1]+dp1[j][i-1])
            }
        }
    }

    return dp2[n][k]
}

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

Algorithm

Используйте dynamic programming для вычисления количества изменений, необходимых для превращения любой подстроки в палиндром.

Используйте еще одно dynamic programming для разбиения строки на k палиндромических подстрок с минимальным количеством изменений.

return минимальное количество изменений, найденное во втором шаге.

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.