Pythonで単調な文字列グループの最小数を見つけるプログラム

小文字の文字列sがあるとします。各部分文字列が増加しないか減少しないように、sが部分に分割される連続する部分文字列の最小数を見つける必要があります。したがって、たとえば、文字列が「pqqqr」のように減少しない文字列であり、「qqqp」が増加しない文字列である場合。

したがって、入力がs ="pqrsrqp"のような場合、出力は2になります。これは、"pqrs"や"rqp"のようなsを壊すことができるためです。

これを解決するには、次の手順に従います-

• sが空の場合、

  • 0を返す

• 最後：=s [0]

• 方向：=1

• カウント：=1

• sの各文字について、実行します

  • char> lastの場合、

    • 方向が1と同じ場合、

      • 方向：=0

    • それ以外の場合、方向が2と同じ場合、

      • 方向：=1

      • count：=count + 1

  • それ以外の場合、char

    • 方向が1と同じ場合、

      • 方向：=2

    • それ以外の場合、方向が0と同じ場合、

      • 方向：=1

      • count：=count + 1

  • 最後：=char

• 返品数

例

理解を深めるために、次の実装を見てみましょう

def solve(s):
   if not s:
      return 0

   last = s[0]
   direction = 1
   count = 1

   for char in s:
      if char > last:
         if direction == 1:
            direction = 0
         elif direction == 2:
            direction = 1
            count += 1
      elif char < last:
         if direction == 1:
            direction = 2
         elif direction == 0:
            direction = 1
            count += 1
      last = char

   return count

s = "pqrsrqp"
print(solve(s))

入力

"pqrsrqp"

出力

2