Κατάργηση Palindromic Subrocences Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα
κορδόνι

Το πρόβλημα Κατάργηση Palindromic Subrocences Leetcode Solution δηλώνει ότι σας δίνεται ένα κορδόνι. Η συμβολοσειρά αποτελείται από δύο μόνο χαρακτήρες "a" ή "b". Πρέπει να διαγράψετε ολόκληρη τη συμβολοσειρά. Υπάρχει ένας περιορισμός που μπορείτε να διαγράψετε μόνο μια παλινδρομική ακολουθία με μία κίνηση. Βρείτε τον ελάχιστο αριθμό βημάτων που απαιτούνται για τη διαγραφή ολόκληρης της συμβολοσειράς. Ας ρίξουμε μια ματιά σε μερικά παραδείγματα πριν προχωρήσουμε στη λύση.

Κατάργηση Palindromic Subrocences Leetcode Solution

s = "ababa"
1

Επεξήγηση: Δεδομένου ότι η συμβολοσειρά είναι ένα περίγραμμα. Μπορούμε να αφαιρέσουμε ολόκληρη τη συμβολοσειρά με μία κίνηση. Έτσι, η απάντηση είναι επίσης 1.

s = "abb"
2

Επεξήγηση: Στην πρώτη κίνηση, καταργούμε το "bb". Στη δεύτερη κίνηση, καταργούμε το "a". Επομένως απαιτούμε τουλάχιστον 2 κινήσεις για να διαγράψουμε ολόκληρη τη συμβολοσειρά.

Προσέγγιση για την κατάργηση Palindromic Subrocences Leetcode Solution

Το πρόβλημα Κατάργηση Palindromic Subrocences Leetcode Solution είναι μια παρατήρηση. Απαιτεί από εμάς να παρατηρήσουμε ότι η συμβολοσειρά αποτελείται από δύο μόνο χαρακτήρες «a» και «b». Εάν συναντήσουμε ένα palindrome, επιστρέφουμε απλώς 1. Επειδή απαιτεί μια μόνο κίνηση για να διαγράψετε ένα ολόκληρο palindrome. Εάν λάβουμε μια κενή συμβολοσειρά, θα πρέπει να επιστρέψουμε το 0. Αλλά εκτός από αυτά, υπάρχει μόνο μία περίπτωση, όταν έχουμε μια συμβολοσειρά που δεν είναι palindrome συνολικά.

Αλλά επειδή η συμβολοσειρά έχει μόνο «a» και «b». Θα κάνουμε το πολύ 2 κινήσεις για να αφαιρέσουμε όλους τους χαρακτήρες. Στην πρώτη κίνηση, πρέπει να αφαιρέσουμε όλα τα. Στη δεύτερη κίνηση, αφαιρούμε όλα τα b. Έτσι, η απάντηση σε αυτό το p [πρόβλημα μπορεί να είναι μόνο 0, 1 ή 2 ανάλογα με την είσοδο.

Κωδικός για κατάργηση Palindromic ακολουθίες Λύση κωδικού Leetcode

Κωδικός C ++

#include <bits/stdc++.h>
using namespace std;

int removePalindromeSub(string s) {
    if(s.size() == 0)
        return 0;

    // check if palindrome
    bool isPalin = true;
    for(int i=0;i<s.length()/2;i++)
        if(s[i] != s[s.length()-1-i])
            isPalin = false;

    if(isPalin == true)
        return 1;
    else
        return 2;
}

int main(){
    cout<<removePalindromeSub("abb");
}
2

Κωδικός Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int removePalindromeSub(String s) {
        if(s.isEmpty())
            return 0;
        
        // check if palindrome
        boolean isPalin = true;
        for(int i=0;i<s.length()/2;i++)
            if(s.charAt(i) != s.charAt(s.length()-1-i))
                isPalin = false;
        
        if(isPalin == true)
            return 1;
        else
            return 2;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(removePalindromeSub("abb"));
  }
}
2

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί πρέπει να περάσουμε από ολόκληρη τη συμβολοσειρά για να ελέγξουμε εάν είναι palindrome ή όχι.

Διαστημική πολυπλοκότητα

Ο (1), γιατί χρησιμοποιούμε έναν σταθερό αριθμό μεταβλητών.