만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

저장 장치

시간 제한2초메모리 제한512 MB

요약
같은 길이의 +와 - 문자열 s와 t가 주어질 때, 인접한 두 구간 중 길이가 다른 짧은 쪽을 뒤집는 연산으로 s를 t로 바꿀 수 있는지 판단합니다.
난이도

보통10점 중 7점

유형
문자열, 시뮬레이션, 그리디
정답자
아직 제출이 없습니다

문제

새로운 디지털 정보 저장 장치를 연구한다. 정보는 셀이라고 부르는 칸들이 한 줄로 늘어선 형태로 저장되며, 각 셀은 두 가지 상태 중 하나를 가진다. 상태는 +와 - 기호로 표시하므로, 셀 하나에 정보 1비트가 담긴다.

같은 상태를 가진 연속된 셀의 묶음을 조각이라고 한다. 조각의 왼쪽에는 셀이 없거나 상태가 반대인 셀이 있고, 오른쪽에도 셀이 없거나 상태가 반대인 셀이 있다.

쓰기 연산에서는 길이가 다른 인접한 조각 두 개를 고를 수 있다. 그다음 두 조각 중 더 짧은 조각에 속한 모든 셀의 상태를 반대로 바꾼다. 이 연산으로 인접한 조각 두 개 또는 세 개가 하나로 합쳐진다.

초기 상태 열과 목표 상태 열이 주어졌을 때, 초기 상태 열에 쓰기 연산을 순서대로 적용해 목표 상태 열을 만들 수 있는지 판별하는 프로그램을 작성하라.

입력

첫 줄에 테스트의 개수 qq가 주어진다. 이어지는 qq개의 줄에는 각각 sis_i와 tit_i가 공백 한 칸으로 구분되어 주어진다. 두 문자열은 비어 있지 않고 길이가 같으며, +와 -로만 이루어져 있다. ii번째 테스트에서는 초기 상태 열 sis_i로부터 목표 상태 열 tit_i를 얻어야 한다.

출력

qq개의 줄을 출력한다. ii번째 줄에는 sis_i로부터 tit_i를 얻을 수 있으면 Yes, 그렇지 않으면 No를 출력한다.

예제2

  1. 예제 1

    입력
    3
++- +++
++-- ++++
++-+--+- ++++++++
    예상 출력
    Yes
No
Yes

  2. 예제 2

    입력
    3
++-+-- ++----
++-+-- +++---
-++- -++-
    예상 출력
    Yes
No
Yes