.append()をすると処理したリストが元に戻ってしまう

Question

#問題

こちらから

#方針
SとTが完全一致の時は明らかなのでexit()します。
隣あうSの二文字を入れ替えた文字列をliに追加していって、最後にTと一致するものがあればYes,なければNoを出力します。
ここでは、liの中身を確認するところまで記述します。

#該当コード

S = list(str(input()))
T = list(str(input()))

if S == T:
	print('Yes')
	exit()

li = []
for i in range(len(S) - 1):
	S[i], S[i + 1] = S[i + 1], S[i]
	li.append(S)
	S[i], S[i + 1] = S[i + 1], S[i]

print(li)

#質問
該当コード中のli.append(S)をprint(S)に変えて試しに出力してみると、

['b', 'a', 'c']
['a', 'c', 'b']

のように期待されたものが得られます。

しかし、上の該当コードを実行すると、例えばS=abc, T=acbのようなテストケースに対して

[['a', 'b', 'c'], ['a', 'b', 'c']]

という出力がされます。
.append()のどのような挙動によって、せっかく処理したSが元通りになってリストに突っ込まれてしまうのでしょうか。素人質問にて恐縮ですが、ご教授のほどよろしくお願い申し上げます。

Answer 1

公式ドキュメント FAQ なぜ list 'y' を変更すると list 'x' も変更されるのですか? で説明されている問題です。

liに1回目にappendしたSと2回目にappendしたSは全く同じリストだからです。

以下のようにコピーを使えば、これを防ぐことができます。

>>> li = []
>>> for i in range(len(S) - 1):
...     S[i], S[i + 1] = S[i + 1], S[i]
...     li.append(S.copy())
...     S[i], S[i + 1] = S[i + 1], S[i]
...
>>> print(li)
[['b', 'a', 'c'], ['a', 'c', 'b']]

Answer 2

質問への直接の回答ではありません。
質問文にある問題を解くコードを書いてみました。

１番目は質問文みあるコードを発展させた方法です。
s の 1 箇所を文字入れ替えしたものをすべて列挙し、t に一致するものがあるか？ を調べています。

２番目は 上の方法では 省メモリーをめざしたものです。li の配列を使わずに済ませています。
３番目は、s == t の比較回数をへらすことをめざしたものです。
s と t を先頭から比べていき、差が出るところをみつけたら、その場所は文字入れ替えになっているかを調べます。もしそうなっていたら、残り部分をお一文字づつ一致するかを調べます。

pppp.pu

def check(s, t):
  if s == t:
    return True

  li = []
  for i in range(len(s) - 1):
    s[i + 1], s[i] = s[i], s[i + 1]
    li.append("".join(s))
    s[i + 1], s[i] = s[i], s[i + 1]

  print("    li=", li)

  str_t = "".join(t)
  for x in li:
    if x == str_t:
      return True
  return False

def check_1(s, t):
  if len(s) != len(t):
    return False

  if s == t:
    return True

  for i in range(len(s) - 1):
    s[i + 1], s[i] = s[i], s[i + 1]
    if s == t:
      return True
    s[i + 1], s[i] = s[i], s[i + 1]

  return False

def check_2(s, t):
  if len(s) != len(t):
    return False

  if s == t:
    return True

  # s と t で差が出る位置を探す
  pos = 0
  for i in range(len(s) - 1):
    if s[i] != t[i]:
      pos = i
      break

  # 文字にお入れ替えになっているか？
  if s[pos] != t[pos + 1] or s[pos + 1] != t[pos]:
      return False

  # 残りの部分はすべて一致するか？
  for i in range(pos + 2, len(s) - 1):
    if s[i] != t[i]:
      return FAlse

  return TRue

# S = list(str(input()))
# T = list(str(input()))

data = [
  ["abc", "acb"],
  ["abc", "abc"],
  ["abc", "ab"],
  ["abc", "abcd"],
  ["abcd", "abcx"],
]

print("--- check")
for d in data:
  s, t = list(d[0]), list(d[1])
  print(d, check(s, t))

print("--- check_1")
for d in data:
  s, t = list(d[0]), list(d[1])
  print(d, check_1(s, t))

print("--- check_2")
for d in data:
  s, t = list(d[0]), list(d[1])
  print(d, check_1(s, t))

実行例