Abbreviation challenge

24 Nov, 2016 Algorithms 0

Problem statement
You can perform the following operation on some string, $a$ :
1. Capitalize zero or more of $a$ ‘s lowercase letters at some index i (i.e., make them uppercase).
2. Delete all of the remaining lowercase letters in $a$ .

Given $q$ queries in the form of two strings, $a$ and $b$ , determine if it’s possible to make $a$
equal to $b$ by performing the above operation on $a$ . If $a$ can be transformed into $b$ ,
print YES on a new line; otherwise, print NO.

Input Format
The first line contains a single integer, $q$ , denoting the number of queries. The $2q$ subsequent lines describe each query in the following format:
1. The first line of each query contains a single string, $a$ .
2. The second line of each query contains a single string, $b$ .

Constraints
$1\le q \le 10$
$1 \le |a|, |b| \le 1000$
String $a$ consists only of uppercase and lowercase English letters.
String $b$ consists only of uppercase English letters.

Output Format
For each query, print YES on a new line if it’s possible to make string $a$ equal to string $b$ by
performing the operation specified above; otherwise, print NO.

Sample Input

1
daBcd
ABC

Sample Output

YES

Explanation
We have $a = daBcd$ and $b = ABC$ . We perform the following operation:
1. Capitalize the letters a and c in $a$ so that $a = dABCd$ .
2. Delete all the remaining lowercase letters in $a$ so that $a = ABC$ .

Because we were able to successfully convert $a$ to $b$ , 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

fizzbuzzer

Looking for good programming challenges?

Abbreviation challenge