← Static tasks

1312. Minimum Insertion Steps to Make a String Palindrome

leetcode

#array#csharp#dynamic-programming#leetcode#math#recursion#string

Task

: hard

Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.

Верните минимальное количество шагов, необходимых для превращения s в палиндром.

Палиндром — это строка, которая читается одинаково как вперед, так и назад.

Пример:

Input: s = "zzazz"

Output: 0

Explanation: The string "zzazz" is already palindrome we do not need any insertions.

C# solution

matched/original
public class Solution {
    private int Lcs(string s1, string s2, int m, int n, int[,] memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m, n] != -1) {
            return memo[m, n];
        }
        if (s1[m - 1] == s2[n - 1]) {
            return memo[m, n] = 1 + Lcs(s1, s2, m - 1, n - 1, memo);
        }
        return memo[m, n] = Math.Max(Lcs(s1, s2, m - 1, n, memo), Lcs(s1, s2, m, n - 1, memo));
    }
    public int MinInsertions(string s) {
        int n = s.Length;
        string sReverse = new string(s.Reverse().ToArray());
        int[,] memo = new int[n + 1, n + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i, j] = -1;
            }
        }
        return n - Lcs(s, sReverse, n, n, memo);
    }
}

C++ solution

auto-draft, review before submit
#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:
    private int Lcs(string s1, string s2, int m, int n, int[,] memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m, n] != -1) {
            return memo[m, n];
        }
        if (s1[m - 1] == s2[n - 1]) {
            return memo[m, n] = 1 + Lcs(s1, s2, m - 1, n - 1, memo);
        }
        return memo[m, n] = max(Lcs(s1, s2, m - 1, n, memo), Lcs(s1, s2, m, n - 1, memo));
    }
    public int MinInsertions(string s) {
        int n = s.size();
        string sReverse = new string(s.Reverse().ToArray());
        int[,] memo = new int[n + 1, n + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i, j] = -1;
            }
        }
        return n - Lcs(s, sReverse, n, n, memo);
    }
}

Java solution

matched/original
class Solution {
    private int lcs(String s1, String s2, int m, int n, int[][] memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m][n] != -1) {
            return memo[m][n];
        }
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
        }
        return memo[m][n] = Math.max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo));
    }

    public int minInsertions(String s) {
        int n = s.length();
        String sReverse = new StringBuilder(s).reverse().toString();
        int[][] memo = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i][j] = -1;
            }
        }

        return n - lcs(s, sReverse, n, n, memo);
    }
}

Go solution

matched/original
func lcs(s1, s2 string, m, n int, memo [][]int) int {
    if m == 0 || n == 0 {
        return 0
    }
    if memo[m][n] != -1 {
        return memo[m][n]
    }
    if s1[m-1] == s2[n-1] {
        memo[m][n] = 1 + lcs(s1, s2, m-1, n-1, memo)
    } else {
        memo[m][n] = max(lcs(s1, s2, m-1, n, memo), lcs(s1, s2, m, n-1, memo))
    }
    return memo[m][n]
}

func minInsertions(s string) int {
    n := len(s)
    sReverse := reverseString(s)
    memo := make([][]int, n+1)
    for i := range memo {
        memo[i] = make([]int, n+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return n - lcs(s, sReverse, n, n, memo)
}

func reverseString(s string) string {
    r := []rune(s)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.

Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.

Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:

Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.

Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].

Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).

В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).

😎