Выдаленне паліндромных паслядоўнасцей з рашэннем штрых-кода


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка
Радок

Праблема "Выдаленне паліндромных паслядоў" з рашэннем штрых-кода абвяшчае, што вам дадзена радок. Радок складаецца толькі з двух сімвалаў "a" ці "b". Вам неабходна сцерці ўвесь радок. Існуе абмежаванне, паводле якога вы можаце выдаліць толькі паліндромную падпасляднасць адным рухам. Знайдзіце мінімальную колькасць крокаў, неабходных для выдалення цэлага радка. Давайце разгледзім некалькі прыкладаў, перш чым пераходзіць да вырашэння.

Выдаленне паліндромных паслядоўнасцей з рашэннем штрых-кода

s = "ababa"
1

Тлумачэнне: Паколькі радок - паліндром. Мы можам выдаліць цэлую радок за адзін ход. Такім чынам, адказ таксама 1.

s = "abb"
2

Тлумачэнне: У першым ходзе мы выдаляем "bb". У другім ходзе мы выдаляем "а". Такім чынам, нам патрабуецца як мінімум 2 хады, каб сцерці ўсю радок.

Падыход да выдалення паліндромных наступстваў рашэннем штрыхкода

Праблема "Выдаленне паліндромных наступстваў" з рашэннем штрых-кода з'яўляецца назіральнай. Патрабуецца заўважыць, што радок складаецца толькі з двух сімвалаў "a" і "b". Калі мы натрапім на паліндром, мы проста вернемся на 1. Паколькі ён патрабуе аднаго руху, каб сцерці ўвесь паліндром. Калі мы атрымліваем пусты радок, мы павінны вярнуць 0. Але акрамя гэтых, ёсць толькі адзінкавы выпадак, калі ў нас ёсць радок, які не з'яўляецца паліндромам у цэлым.

Але паколькі радок мае толькі "a" і "b". Мы зробім не больш за 2 хады, каб выдаліць усіх персанажаў. У першым ходзе мы павінны выдаліць усе "а". У другім ходзе мы выдаляем усе "b". Такім чынам, адказ на гэтую р [праблему можа быць толькі 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

Аналіз складанасці

Складанасць часу

O (N), таму што нам трэба прайсці ўвесь радок, каб праверыць, паліндром гэта ці не.

Касмічная складанасць

O (1), таму што мы выкарыстоўваем пастаянную колькасць зменных.