Python에서 주어진 제약 조건으로 한 문자열을 다른 문자열로 변환할 수 있는지 확인

<시간/>

세 개의 문자 'A', 'B' 및 '#'만 있는 두 개의 문자열 s와 t가 있다고 가정합니다. s에 대해 이러한 연산을 수행하여 s를 t로 변환할 수 있는지 확인해야 합니다.

'A'는 왼쪽으로만 이동할 수 있습니다.
'B'는 오른쪽으로만 이동할 수 있습니다.
'A'와 'B'는 서로 교차할 수 없습니다.

따라서 입력이 s ="##AB##B" t ="A###B#B"와 같으면 출력은 True가 됩니다. 오른쪽으로 한 단계 이동할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

s :=s에서 문자를 가져오는 목록
t :=t에서 문자를 가져오는 목록
s의 크기가 t의 크기와 같지 않으면
- 거짓을 반환
s와 t에서 'A'의 개수가 다르거나 s와 t에서 'B'의 개수가 다르거나,
- 거짓을 반환
0 ~ s - 1 크기 범위의 i에 대해
- s[i]가 '#'과 같지 않으면
  - 0에서 t - 1 사이의 범위에 있는 j에 대해 다음을 수행합니다.
    - (t[j]가 s[i]와 같지 않음) 및 t[j]가 '#'과 같지 않으면
      - 거짓을 반환
    - t[j]가 s[i]와 같으면
      - t[j] :='#'
      - s[i]가 'A'와 같고 i
      - 거짓을 반환
    - s[i]가 'B'와 같고 i> j이면
      - 거짓을 반환
    - 루프에서 나오다

참 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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