ลบ Palindromic Subsequences Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน
เชือก

ปัญหาลบ Palindromic Subsequences Leetcode Solution ระบุว่าคุณได้รับไฟล์ เชือก. สตริงประกอบด้วยอักขระ "a" หรือ "b" เพียงสองตัว คุณจะต้องลบสตริงทั้งหมด มีข้อ จำกัด ที่คุณสามารถลบเฉพาะลำดับต่อมาของ palindromic ในการย้ายครั้งเดียว ค้นหาจำนวนขั้นต่ำที่จำเป็นในการลบสตริงทั้งหมด ให้เราดูตัวอย่างบางส่วนก่อนที่จะกระโดดลงไปในการแก้ปัญหา

ลบ Palindromic Subsequences Leetcode Solution

s = "ababa"
1

คำอธิบาย: เนื่องจากสตริงเป็นพาลินโดรม เราสามารถลบสตริงทั้งหมดได้ในครั้งเดียว ดังนั้นคำตอบก็คือ 1

s = "abb"
2

คำอธิบาย: ในการย้ายครั้งแรกเราจะลบ“ bb” ในการย้ายครั้งที่สองเราจะลบ“ a” ดังนั้นเราต้องมีการเคลื่อนไหวอย่างน้อย 2 ครั้งเพื่อลบสตริงทั้งหมด

แนวทางในการลบ Palindromic Subsequences Leetcode Solution

ปัญหา Remove Palindromic Subsequences Leetcode Solution เป็นข้อสังเกตอย่างหนึ่ง เราต้องสังเกตว่าสตริงประกอบด้วยอักขระ 'a' และ 'b' เพียงสองตัว ถ้าเราเจอพาลินโดรมเราก็กลับ 1 เพราะมันต้องใช้การย้ายครั้งเดียวเพื่อลบพาลินโดรมทั้งหมด ถ้าเราได้สตริงว่างเราควรคืนค่า 0 แต่นอกเหนือจากนี้มีเพียงกรณีเดียวเมื่อเรามีสตริงที่ไม่ใช่ palindrome โดยรวม

แต่เนื่องจากสตริงมีเพียง "a" และ "b" เราจะใช้เวลามากที่สุด 2 ท่าในการลบตัวละครทั้งหมด ในการย้ายครั้งแรกเราควรลบ 'a ทั้งหมดออก ในการย้ายครั้งที่สองเราจะลบ 'b ทั้งหมดออก ดังนั้นคำตอบสำหรับ p [ปัญหานี้สามารถเป็นได้เพียง 0, 1 หรือ 2 ขึ้นอยู่กับอินพุต

รหัสเพื่อลบ Palindromic ผลที่ตามมา Leetcode Solution

รหัส 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 หรือไม่

ความซับซ้อนของอวกาศ

O (1), เนื่องจากเราใช้ตัวแปรจำนวนคงที่