删除回文子序列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。

删除回文子序列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

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), 因为我们使用恒定数量的变量。