محلول Leetcode Palindromic عواقب را حذف کنید


سطح دشواری ساده
اغلب در آمازون
رشته

مشكل Remove Palindromic عواقب Leetcode Solution بیان می كند كه به شما داده می شود رشته. این رشته فقط از دو حرف 'a' یا 'b' تشکیل شده است. شما باید کل رشته را پاک کنید. محدودیتی وجود دارد که شما می توانید فقط یک دنباله پالیندرومیک را در یک حرکت حذف کنید. حداقل تعداد مراحل لازم برای پاک کردن کل رشته را پیدا کنید. قبل از ورود به راه حل ، اجازه دهید نگاهی به چند مثال بیندازیم.

محلول Leetcode Palindromic عواقب را حذف کنید

s = "ababa"
1

توضیح: از آنجا که رشته یک پلیندروم است. ما می توانیم در یک حرکت کل رشته را حذف کنیم. بنابراین پاسخ نیز 1 است.

s = "abb"
2

توضیح: در اولین حرکت ، "bb" را حذف می کنیم. در حرکت دوم ، "a" را حذف می کنیم. بنابراین برای پاک کردن کل رشته حداقل به 2 حرکت نیاز داریم.

رویکرد برای حذف محلول Leetcode متعاقب Palindromic

مسئله حذف Palindromic عواقب Leetcode Solution یک مسئله مشاهده است. این ما را ملزم می کند تا مشاهده کنیم که این رشته فقط از دو نویسه "a" و "b" تشکیل شده است. اگر به یک پالیندروم برخورد کنیم ، به سادگی برمی گردیم 1. زیرا برای پاک کردن یک پالیندروم کامل به یک حرکت نیاز دارد. اگر یک رشته خالی بدست آوریم ، باید 0 را برگردانیم. اما غیر از اینها ، فقط یک مورد وجود دارد ، وقتی رشته ای داشته باشیم که به طور کلی پالیندروم نباشد.

اما از آنجا که این رشته فقط "a" و "b" دارد. حداکثر 2 حرکت برای حذف همه کاراکترها انجام خواهیم داد. در اولین حرکت ، باید همه "a" ها را حذف کنیم. در حرکت دوم ، همه "b" را حذف می کنیم. بنابراین پاسخ این p [مسئله می تواند بسته به ورودی فقط 0 ، 1 یا 2 باشد.

کد حذف محلول Leetcode متعاقب Palindromic

کد 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

کد جاوا

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) ، زیرا ما از تعداد ثابت متغیرها استفاده می کنیم.