刪除回文子序列Leetcode解決方案


難度級別 容易獎學金
經常問 亞馬遜

問題刪除回文子序列Leetcode解決方案指出,您得到了。 該字符串僅包含兩個字符“ a”或“ b”。 您需要擦除整個字符串。 有一個限制,即您只能一口氣刪除回文子序列。 找到擦除整個字符串所需的最小步驟數。 在進入解決方案之前,讓我們看一些示例。

刪除回文子序列Leetcode解決方案

s = "ababa"
1

說明:由於字符串是回文。 我們只需一步即可刪除整個字符串。 因此答案也是1。

s = "abb"
2

說明:首先,我們刪除“ bb”。 在第二步中,我們刪除“ a”。 因此,我們至少需要2步才能擦除整個字符串。

刪除回文序列Leetcode解決方案的方法

問題“刪除回文子序列Leetcode解決方案”是一個發現。 它要求我們觀察到該字符串僅由兩個字符“ a”和“ b”組成。 如果遇到回文,我們只返回1。因為只需一步即可刪除整個回文。 如果我們得到一個空字符串,我們應該返回0。但是,除了這些字符串外,當我們擁有的字符串不是回文整體時,只有一種情況。

但是由於字符串只有“ a”和“ b”。 我們最多只能採取2步來刪除所有字符。 第一步,我們應該刪除所有的“ a”。 在第二步中,我們刪除所有的“ 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(1), 因為我們使用恆定數量的變量。