各パーティションがPythonでアナグラムを形成するように2つの文字列をパーティション化するプログラム

同じ長さの2つの空でない文字列sとtがあるとします。 sとtの部分文字列の各ペアが同じサイズであり、それらが互いにアナグラムになるように、それらを部分文字列に分割する必要があります。ここで、sとtのカット数が最大になるようなカットインデックスを見つけます。結果が見つからない場合は、空のリストを返します。

したがって、入力がs ="bowcattiger" t ="owbactietgr"の場合、出力は[0、3、5、6、10]になります。これは、各文字列がお互いのアナグラム。 s =["bow"、 "ca"、 "t"、 "tige"、 "r"]、t =["owb"、 "ac"、 "t"、 "ietg"、 "r"]

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

• 間隔：=新しいリスト
• cs：=sに文字が存在するマップとその頻度
• ct：=tに存在する文字とその頻度を含むマップ
• csがctと同じでない場合、
  • 新しいリストを返す
• s-1から0までの範囲サイズのxの場合、実行
  • cs [s [x]]：=cs [s [x]]-1
  • ct [t [x]]：=ct [t [x]]-1
  • csがctと同じ場合、
    • 間隔の最後にxを挿入
• リストの間隔を並べ替えて返す

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

例

from collections import Counter
class Solution:
   def solve(self, a, b):
      intervals = []
      ca = Counter(a)
      cb = Counter(b)
      if ca != cb:
         return []
      for x in reversed(range(len(a))):
            ca[a[x]] -= 1
            cb[b[x]] -= 1
            if ca == cb:
               intervals.append(x)
      return sorted(intervals)
ob = Solution()
s = "bowcattiger"
t = "owbactietgr"
print(ob.solve(s, t))

入力

"bowcattiger", "owbactietgr"

出力

[0, 3, 5, 6, 10]