Pythonを使用して、1つの文字列スワップで文字列を等しくできるかどうかを確認するプログラム

同じ長さの2つの文字列sとtがあるとします。文字列内の2つのインデックス（必ずしも異なる必要はありません）を選択し、選択したインデックスの文字を交換する操作について考えてみます。正確に1つの文字列に対して最大で1つの文字列スワップを実行することにより、両方の文字列を同じにすることができるかどうかを確認する必要があります。

したがって、入力がs ="hello" t ="hlelo"の場合、sまたはtのいずれかで「e」と「l」を入れ替えて等しくする必要があるため、出力はTrueになります。

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

• max_diffs：=2

• diffs：=0

• st：=新しいセット

• st2：=新しいセット

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

  • s[i]がt[i]と同じでない場合、

    • diffs：=diffs + 1

  • s [i]がstに存在しない場合、

    • s[i]をstに挿入します

  • t [i]がst2に存在しない場合、

    • t[i]をst2に挿入します

  • diffs> max_diffsの場合、

    • Falseを返す

• （diffsが0またはdiffsが2と同じ）、stのサイズがst2のサイズと同じで、stがst2と同じ場合、trueを返します。それ以外の場合はfalse

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

例

def solve(s, t):
   max_diffs=2
   diffs=0
   st = set()
   st2 = set()
   for i in range(len(s)):
      if s[i] != t[i]:
         diffs+=1
      if s[i] not in st:
         st.add(s[i])
      if t[i] not in st2:
         st2.add(t[i])
      if diffs > max_diffs:
         return False
   return (diffs == 0 or diffs == 2) and len(st) == len(st2) and st == st2
s = "hello"
t = "hlelo"
print(solve(s, t))

入力

"hello", "hlelo"

出力

True