【LeetCode日記】1332.テキスト・サブシーケンスの削除

タイトルアドレス(1332.返信サブシーケンスの削除)
https://leetcode-cn.com/probl...
タイトルの説明

              （     ）       。

「   」  ：                                ，                   。

「  」  ：                 ，             。

 

   1：

  ：s = "ababa"
  ：1
  ：           ，       。
   2：

  ：s = "abb"
  ：2
  ："abb" -> "bb" -> "".
         "a"，      "bb"。
   3：

  ：s = "baabb"
  ：2
  ："baabb" -> "b" -> "".
         "baab"，      "b"。
   4：

  ：s = ""
  ：0
 

  ：

0 <= s.length <= 1000
s       'a'    'b'
             ？

構想
これはまた1本の“震える機転が利く”のテーマで、類似のテーマは1297.maximum-number-of-occurrences-of-a-substringあります
aとbの2文字しかないからです.実は一番多い消去回数は2です.私たちはどうしてもすべての1を消してからすべての2を消すことができます(先に2を消しても同じです)、このように2回で完成することができます.私たちはもう一度テーマの1回の除去の情況を見て、テーマの与える例は“ababa”で、私達は実はそれ自身が1つの回文の列であることを発見して、だからやっと一回すべて取り除くことができます.では、考え方は次のとおりです.

sが返信であれば、

を削除する必要があります.

そうでないと

が2回必要です

特殊な状況に注意してください.空の文字列については、0回の

が必要です.
コード#コード#
コードサポート:Python 3
Python3 Code:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == '':
            return 0
        def isPalindrome(s):
            l = 0
            r = len(s) - 1
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        return 1 if isPalindrome(s) else 2

返信文が本題のポイントではないと判断した場合は、簡単に実現できます.
Python3 Code:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == '':
            return 0
        return 1 if s == s[::-1] else 2

キー解析

問題を審査することに注意して、必ず問題の条件を利用して“aとbの2つの文字だけを含みます”さもなくばやりやすいのは面倒です