Отстранете го растворот на летен код за палинндромични последици


Ниво на тешкотија Лесно
Често прашувано во Амазон
Стринг

Проблемот Отстрани палиндромични последици Leetcode решение вели дека ти е дадена a низа. Низата се состои од само два знака 'a' или 'b'. Од вас се бара да ја избришете целата низа. Постои ограничување дека можете да избришете само палиндромична репродукција со еден потег. Пронајдете го минималниот број чекори потребни за бришење на целата низа. Ајде да погледнеме неколку примери пред да скокнеме во решението.

Отстранете го растворот на летен код за палинндромични последици

s = "ababa"
1

Објаснување: Бидејќи низата е палиндром. Можеме да ја отстраниме целата низа со еден потег. Така, одговорот е исто така 1.

s = "abb"
2

Објаснување: Во првиот потег, го отстрануваме „bb“. Во вториот потег, го отстрануваме „а“. Така, потребни ни се најмалку 2 потези за да ја избришеме целата низа.

Пристап кон отстранување на растворот за летен код за палинндромични последици

Проблемот Отстрани палиндромични последици Leetcode решение е набудување. Потребно е да забележиме дека низата се состои од само два знака „а“ и „б“. Ако наидеме на палиндром, едноставно враќаме 1. Бидејќи бара единствен потег за да се избрише целиот палиндром. Ако добиеме празна низа, треба да вратиме 0. Но, освен овие, има само еден случај, кога имаме низа што не е палиндром како целина.

Но, бидејќи низата има само 'а' и 'б'. Willе преземеме најмногу 2 потези за да ги отстраниме сите знаци. Во првиот потег, треба да ги отстраниме сите „а“. Во вториот потег, ги отстрануваме сите 'b'. Така, одговорот на овој p [проблем може да биде само 0, 1 или 2 во зависност од влезот.

Код за отстранување на раствор на летен код за палинндромични последици

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

Анализа на сложеност

Временска комплексност

НА), затоа што треба да ја поминеме целата низа за да провериме дали е палиндром или не.

Комплексноста на просторот

О (1), затоа што користиме постојан број на променливи.