Palindromic Subsequences Leetcode 솔루션 제거


난이도 쉽게
자주 묻는 질문 아마존

Palindromic Subsequences Leetcode Solution 제거 문제는. 문자열은 'a'또는 'b'두 문자로만 구성됩니다. 전체 문자열을 지워야합니다. 한 번의 이동으로 회문 하위 시퀀스 만 삭제할 수 있다는 제한이 있습니다. 전체 문자열을 지우는 데 필요한 최소 단계 수를 찾으십시오. 솔루션을 시작하기 전에 몇 가지 예를 살펴 보겠습니다.

Palindromic Subsequences Leetcode 솔루션 제거

s = "ababa"
1

설명 : 문자열이 회문이기 때문입니다. 한 번의 움직임으로 전체 문자열을 제거 할 수 있습니다. 따라서 답도 1입니다.

s = "abb"
2

설명 : 첫 번째 이동에서 "bb"를 제거합니다. 두 번째 이동에서는 "a"를 제거합니다. 따라서 전체 문자열을 지우려면 최소 2 개의 동작이 필요합니다.

Palindromic Subsequences 제거 Leetcode 솔루션에 대한 접근 방식

Palindromic Subsequences Leetcode Solution 제거 문제는 관찰 문제입니다. 문자열이 'a'와 'b'두 문자로만 구성되어 있음을 관찰해야합니다. 회문을 발견하면 1을 반환합니다. 회문 전체를 지우려면 한 번의 움직임이 필요하기 때문입니다. 빈 문자열을 얻으면 0을 반환해야합니다. 그러나 이것 외에는 전체적으로 회문이 아닌 문자열이있을 때 단 하나의 경우 만 있습니다.

그러나 문자열에는 'a'와 'b'만 있기 때문에. 우리는 모든 캐릭터를 제거하기 위해 최대 2 개의 이동을 할 것입니다. 첫 번째 이동에서 우리는 모든 'a'를 제거해야합니다. 두 번째 이동에서는 모든 'b'를 제거합니다. 따라서이 p [문제에 대한 답은 입력에 따라 0, 1 또는 2 일 수 있습니다.

Palindromic Subsequences 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

자바 코드

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 (1), 상수의 변수를 사용하기 때문입니다.