While browsing through some questions on www.codeforces.com I came across this question and decided to solve it. I wanted to share my solution to this fairly simple problem with you all.

The Question:

You are given two strings of equal length ss and tt consisting of lowercase Latin letters. You may perform any number (possibly, zero) operations on these strings.

During each operation you choose two adjacent characters in any string and assign the value of the first character to the value of the second or vice versa.

For example, if s is “acbc” you can get the following strings in one operation:

“aabc” (if you perform s2=s1s2=s1);

“ccbc” (if you perform s1=s2s1=s2);

“accc” (if you perform s3=s2s3=s2 or s3=s4s3=s4);

“abbc” (if you perform s2=s3s2=s3);

“acbb” (if you perform s4=s3s4=s3);

Note that you can also apply this operation to the string t.

Please determine whether it is possible to transform s into t, applying the operation above any number of times.

Note that you have to answer q independent queries.

Input

The first line contains one integer q (1≤q≤1001≤q≤100) — the number of queries. Each query is represented by two consecutive lines.

The first line of each query contains the string ss (1≤|s|≤1001≤|s|≤100) consisting of lowercase Latin letters.

The second line of each query contains the string t (1≤|t|≤1001≤|t|≤100, |t|=|s||t|=|s|) consisting of lowercase Latin letters.

Output

For each query, print “YES” if it is possible to make ss equal to t, and “NO” otherwise.

You may print every letter in any case you want (so, for example, the strings “yEs”, “yes”, “Yes”, and “YES” will all be recognized as positive answer).

The Approach:

Since this problem requires us to simply check if the given operation is possible, it becomes a relatively easy problem.

Let’s start with an analytic approach.

What condition must be satisfied for it to be possible to convert s1 to s2.

If we look at it, we realize that the only condition where this is not possible is when there are no common letters between the 2 strings.

Therefore, the solution gets reduced to a very simple algorithm.

Just check if there is any common letter among the two strings and print the appropriate message.

The Program:

The program for this question is given below (in python):

q = int(input())
ans = []
for i in range(q):
    s1 = input()
    s2 = input()
    fl = 0
    for j in s1:
        if j in s2:
            fl = 1
            break
    if fl==0:
        ans.append("NO")
    else:
        ans.append("YES")
for i in ans:
    print(i)

The output of the above program is given below:

This concludes today’s blog.

Stay tuned for more!

Visits: 113

Leave a Reply

Your email address will not be published. Required fields are marked *