文字列がPythonの部分文字列ソート操作で変換可能かどうかをチェックするプログラム

2つの数値文字列sとtがあるとします。次の操作を何度でも使用して、文字列sからtに変換します。1。sで空でない部分文字列を選択し、文字が昇順になるようにインプレースで並べ替えます。文字列sを文字列tに変換できるかどうかを確認する必要があります。

したがって、入力がs ="95643" t ="45963"の場合、 "95643"-> "95463"-> "45963"のようにsをtに変換できるため、出力はTrueになります。

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

• Places：=デフォルト値タイプがリストであるマップ

• sから0までの範囲サイズのiの場合、実行します

  • key：=s [i] as integer

  • 場所の最後にiを挿入[キー]

• tの各eについて、実行します

  • key：=e as integer

    • Places [key]が空の場合、

      • Falseを返す

    • i：=場所の最後の要素[キー]

    • 範囲0からキー-1のjの場合、実行

      • Places [j]が空ではなく、places [j]

        • Falseを返す

    • Places [key]

      から最後の要素を削除します

• Trueを返す

例

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

from collections import defaultdict
def solve(s, t):
   places = defaultdict(list)
   for i in reversed(range(len(s))):
      key = int(s[i])
      places[key].append(i)

   for e in t:
      key = int(e)
      if not places[key]:
         return False
      i = places[key][-1]
      for j in range(key):
         if places[j] and places[j][-1] < i:
            return False
      places[key].pop()
   return True

s = "95643"
t = "45963"
print(solve(s, t))

入力

"95643", "45963"

出力

True