1332. Remove Palindromic Subsequences

LeetCode easy оригинал: C# #array #csharp #easy #leetcode #string

LeetCode Static

Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s.

Верните минимальное количество шагов, чтобы сделать данную строку пустой.

Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной.

Строка называется палиндромом, если она читается одинаково как вперед, так и назад.

Пример:

Input: s = "ababa"

Output: 1

Explanation: s is already a palindrome, so its entirety can be removed in a single step.

C# решение

сопоставлено/оригинал

public class Solution {
    public int RemovePalindromeSub(string s) {
        if (string.IsNullOrEmpty(s)) {
            return 0;
        }
        if (new string(s.Reverse().ToArray()) == s) {
            return 1;
        }
        return 2;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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 RemovePalindromeSub(string s) {
        if (string.IsNullOrEmpty(s)) {
            return 0;
        }
        if (new string(s.Reverse().ToArray()) == s) {
            return 1;
        }
        return 2;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int RemovePalindromeSub(String s) {
        if (String.IsNullOrEmpty(s)) {
            return 0;
        }
        if (new String(s.Reverse().ToArray()) == s) {
            return 1;
        }
        return 2;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        if s == s[::-1]:
            return 1
        return 2

Go решение

сопоставлено/оригинал

func removePalindromeSub(s string) int {
    if len(s) == 0 {
        return 0
    }
    reversedString := reverseString(s)
    if reversedString == s {
        return 1
    }
    return 2
}

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

Algorithm

Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг.

Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот).

Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.