Pythonの特定の条件に従って、2つの文字列が同等であるかどうかを確認します

同じサイズの2つの文字列sとtがあるとします。 sとtが等しいかどうかを確認する必要があります。チェックする条件はいくつかあります：

• どちらも同じです。または、
• sを同じサイズの2つの連続する部分文字列に分割し、その部分文字列がs1とs2であり、同じようにtをt1とt2に分割する場合、次のいずれかが有効である必要があります。
  • s1は再帰的にt1と同等であり、s2は再帰的にt2と同等です
  • s1は再帰的にt2と同等であり、s2は再帰的にt1と同等です

したがって、入力がs ="ppqp" t ="pqpp"の場合、出力は、sとtを2つの部分に分割するかのようにTrueになります。s1="pp"、s2 ="qp"、t1 ="pq "、t2 =" pp "、ここではs1 =t2であり、s2とt1を2つの部分に分割するとs21 =" q "、s22 =" p "、t11 =" p "、t12 =" q "、ここでもs21 =t12とs22=t11なので、再帰的に同等です。

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

• 関数util（）を定義します。これには時間がかかります
• sのサイズが奇数の場合、
  • return s
• left：=util（sの左半分）
• right：=util（sの右半分）
• （左連結右）、（右連結左）の最小値を返します
• メインメソッドから、util（s）がutil（t）と同じ場合はtrueを返し、それ以外の場合はfalseを返します

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

サンプルコード

def util(s):
   if len(s) & 1 != 0:
      return s
 
   left = util(s[0:int(len(s) / 2)])
   right = util(s[int(len(s) / 2):len(s)])
 
   return min(left + right, right + left)
 
def solve(s,t):
   return util(s) == util(t)

s = "ppqp"
t = "pqpp"
print(solve(s, t))

入力

"ppqp", "pqpp"

出力

True