Abbreviation challenge
Problem statement
You can perform the following operation on some string, :
1. Capitalize zero or more of ‘s lowercase letters at some index i (i.e., make them uppercase).
2. Delete all of the remaining lowercase letters in .
Given queries in the form of two strings,
and
, determine if it’s possible to make
equal to by performing the above operation on
. If
can be transformed into
,
print YES
on a new line; otherwise, print NO
.
Input Format
The first line contains a single integer, , denoting the number of queries. The
subsequent lines describe each query in the following format:
1. The first line of each query contains a single string, .
2. The second line of each query contains a single string, .
Constraints
String consists only of uppercase and lowercase English letters.
String consists only of uppercase English letters.
Output Format
For each query, print YES
on a new line if it’s possible to make string equal to string
by
performing the operation specified above; otherwise, print NO
.
Sample Input
1 daBcd ABC
Sample Output
YES
Explanation
We have and
. We perform the following operation:
1. Capitalize the letters a and c in so that
.
2. Delete all the remaining lowercase letters in so that
.
Because we were able to successfully convert to
, we print
YES
on a new line.
Solution
import sys def solve(a,b): if len(b) > len(a): print("NO") else: i = 0 # index for a j = 0 # index for b n = len(a) dp = [False for x in range(len(b))] while i < n: found = False while i < n and a[i].upper() != b[j]: if a[i].isupper() and b[j-1] != a[i]: print("NO") return i = i + 1 if i < len(a): found = True if found: dp[j] = True j = j + 1 if j == len(b): break i = i + 1 if dp[-1]: # Check if all a's remaining characters are lowercase # (because we can only delete remaining lowercase chars) for c in a[i+1:]: if c.isupper() and b[j-1] != c: print("NO") return print("YES") else: print("NO") def main(): f = open("in5.txt") queries = int(f.readline()) for q in range(0, queries): a = f.readline().strip() b = f.readline().strip() solve(list(a),list(b)) main()
Notebook file
https://github.com/lucaslouca/coding-problems/tree/master/python/Abbreviation