Pythonで特定の制約を使用して、ある文字列を別の文字列に変換できるかどうかを確認します

「A」、「B」、「＃」の3文字のみの2つの文字列sとtがあるとします。 sに対してこれらの操作を実行することにより、sをtに変換できるかどうかを確認する必要があります。

• 「A」は左側にのみ移動できます
• 「B」は右側にのみ移動できます
• 「A」も「B」も互いに交差することはできません

したがって、入力がs ="## AB ## B" t ="A ### B＃B"の場合、出力はTrueになります。これは、s Aが左端の位置に簡単に移動でき、中央のBが簡単に移動できるためです。右に1ステップ移動できます

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

• s：=sから文字を取得したリスト
• t：=tから文字を取得したリスト
• sのサイズがtのサイズと同じでない場合、
  • Falseを返す
• sとtの「A」の数が異なる場合、またはsとtの「B」の数が異なる場合、または
  • Falseを返す
• 範囲0からs-1のサイズのiの場合、do
  • s [i]が'＃'と同じでない場合、
    • 範囲0からt-1のサイズのjの場合、do
      • （t[j]がs[i]と同じではない）およびt[j]が「＃」と同じでない場合
        • Falseを返す
      • t[j]がs[i]と同じ場合、
        • t [j]：='＃'
        • s[i]が'A'と同じでi
        • Falseを返す
      • s[i]が'B'およびi>jと同じである場合、
        • Falseを返す
      • ループから抜け出す

例

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

def solve(s, t):
   s = list(s)
   t = list(t)
   if len(s) != len(t):
      return False
   if s.count('A') != t.count('A') or s.count('B') != t.count('B'):
      return False
   for i in range(len(s)):
      if s[i] != '#':
         for j in range(len(t)):
            if (t[j] != s[i]) and t[j] != '#':
               return False
            if t[j] == s[i]:
               t[j] = '#'
               if s[i] == 'A' and i < j:
                  return False
               if s[i] == 'B' and i > j:
                  return False
               break
   return True
s = "##AB##B"
t = "A###B#B"
print (solve(s, t))

入力

"##AB##B", "A###B#B"

出力

True