516. Longest Palindromic Subsequence

leetcode medium

#array#csharp#dynamic-programming#hash-table#leetcode#math#medium#recursion#string

Task

Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s.

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.

Пример:

Input: s = "bbbab"

Output: 4

Explanation: One possible longest palindromic subsequence is "bbbb".

C# solution

matched/original

public class Solution {
    public int LongestPalindromeSubseq(string s) {
        int n = s.Length;
        var memo = new Dictionary<(int, int), int>();
        
        int Lps(int l, int r) {
            if (memo.ContainsKey((l, r))) return memo[(l, r)];
            if (l > r) return 0;
            if (l == r) return 1;
            
            int res;
            if (s[l] == s[r]) {
                res = Lps(l + 1, r - 1) + 2;
            } else {
                res = Math.Max(Lps(l, r - 1), Lps(l + 1, r));
            }
            memo[(l, r)] = res;
            return res;
        }
        
        return Lps(0, n - 1);
    }
}

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:
    public int LongestPalindromeSubseq(string s) {
        int n = s.size();
        var memo = new unordered_map<(int, int), int>();
        
        int Lps(int l, int r) {
            if (memo.count((l, r))) return memo[(l, r)];
            if (l > r) return 0;
            if (l == r) return 1;
            
            int res;
            if (s[l] == s[r]) {
                res = Lps(l + 1, r - 1) + 2;
            } else {
                res = max(Lps(l, r - 1), Lps(l + 1, r));
            }
            memo[(l, r)] = res;
            return res;
        }
        
        return Lps(0, n - 1);
    }
}

Java solution

matched/original

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        Map<String, Integer> memo = new HashMap<>();
        
        int lps(int l, int r) {
            String key = l + "," + r;
            if (memo.containsKey(key)) return memo.get(key);
            if (l > r) return 0;
            if (l == r) return 1;
            
            int res;
            if (s.charAt(l) == s.charAt(r)) {
                res = lps(l + 1, r - 1) + 2;
            } else {
                res = Math.max(lps(l, r - 1), lps(l + 1, r));
            }
            memo.put(key, res);
            return res;
        }
        
        return lps(0, n - 1);
    }
}

JavaScript solution

matched/original

var longestPalindromeSubseq = function(s) {
    const n = s.length;
    const memo = new Map();
    
    const lps = (l, r) => {
        const key = `${l},${r}`;
        if (memo.has(key)) return memo.get(key);
        if (l > r) return 0;
        if (l === r) return 1;
        
        let res;
        if (s[l] === s[r]) {
            res = lps(l + 1, r - 1) + 2;
        } else {
            res = Math.max(lps(l, r - 1), lps(l + 1, r));
        }
        memo.set(key, res);
        return res;
    };
    
    return lps(0, n - 1);
};

Python solution

matched/original

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        memo = {}
        
        def lps(l, r):
            if (l, r) in memo:
                return memo[(l, r)]
            if l > r:
                return 0
            if l == r:
                return 1

            if s[l] == s[r]:
                memo[(l, r)] = lps(l + 1, r - 1) + 2
            else:
                memo[(l, r)] = max(lps(l, r - 1), lps(l + 1, r))
            return memo[(l, r)]

        return lps(0, n - 1)

Go solution

matched/original

func longestPalindromeSubseq(s string) int {
    n := len(s)
    memo := make(map[[2]int]int)
    
    var lps func(int, int) int
    lps = func(l, r int) int {
        if val, ok := memo[[2]int{l, r}]; ok {
            return val
        }
        if l > r {
            return 0
        }
        if l == r {
            return 1
        }
        
        if s[l] == s[r] {
            memo[[2]int{l, r}] = lps(l + 1, r - 1) + 2
        } else {
            memo[[2]int{l, r}] = max(lps(l, r - 1), lps(l + 1, r))
        }
        return memo[[2]int{l, r}]
    }
    
    return lps(0, n - 1)
}

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

Explanation

Algorithm

Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎