삭제형 편집

면접 대비

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

요약

두 단어 s와 t가 주어질 때, 호명된 글자의 첫 번째 등장을 반복해서 지우면 s에서 t를 만들 수 있는지 판별합니다.

난이도: 보통10점 중 5점
유형: 문자열, 구현
정답자: 아직 제출이 없습니다

문제

데이지는 단어로 하는 게임을 좋아한다. 최근 데이지는 다니엘과 아래의 삭제형 편집(Deletive Editing) 게임을 하고 있다.

데이지가 단어를 하나 고른다. 예를 들어 DETERMINED이다. 매 턴마다 다니엘이 알파벳을 하나 부르면, 데이지는 단어에서 그 글자가 처음 나오는 자리를 지운다. 다니엘이 E를 부르면 DTERMINED가 된다. 다음 턴에 다니엘이 D를 부르면 첫 번째 D가 지워져 TERMINED가 된다. 이어서 I를 부르면 TERMNED, N을 부르면 TERMED, D를 부르면 TERME가 된다. 이때 다니엘이 E를 부르면 데이지는 TRME를 얻는다. 그러나 DETERMINED에서 시작하면 TERM을 얻을 방법이 없다.

데이지는 주어진 초기 단어에서 게임을 0번 이상 진행해 원하는 최종 단어를 얻을 수 있는지 알고 싶어 한다. 그 가능 여부를 판별하라.

입력

첫 줄에 테스트 케이스의 수 $n$ 이 주어진다 ( $1 \le n \le 10\,000$ ). 이어지는 $n$ 개의 줄에는 공백으로 구분된 두 단어 $s$ 와 $t$ 가 한 줄에 하나씩 주어진다. 각 단어는 1자 이상 30자 이하의 대문자 영어 알파벳으로 이루어진다. $s$ 는 데이지의 초기 단어이고, $t$ 는 데이지가 얻고자 하는 최종 단어이다.

출력

각 테스트 케이스마다 한 줄을 출력한다. 게임을 진행해 $s$ 에서 $t$ 를 얻을 수 있으면 YES를, 없으면 NO를 출력한다.

예제1

예제 1

입력

6
DETERMINED TRME
DETERMINED TERM
PSEUDOPSEUDOHYPOPARATHYROIDISM PEPA
DEINSTITUTIONALIZATION DONATION
CONTEST CODE
SOLUTION SOLUTION

예상 출력

YES
NO
NO
YES
NO
YES