Cerinta completa

You can perform the following operations on the string, :

  1. Capitalize zero or more of ‘s lowercase letters.
  2. Delete all of the remaining lowercase letters in .

Given two strings, and , determine if it’s possible to make equal to as described. If so, print YES on a new line. Otherwise, print NO.

For example, given and , in we can convert and delete to match . If and , matching is not possible because letters may only be capitalized or discarded, not changed.

Function Description

Complete the function in the editor below. It must return either or .

abbreviation has the following parameter(s):

  • a: the string to modify
  • b: the string to match

Input Format

The first line contains a single integer , the number of queries.

Each of the next pairs of lines is as follows:
– The first line of each query contains a single string, .
– The second line of each query contains a single string, .

Constraints

  • String consists only of uppercase and lowercase English letters, ascii[A-Za-z].
  • String consists only of uppercase English letters, ascii[A-Z].

Output Format

For each query, print YES on a new line if it’s possible to make string equal to string . Otherwise, print NO.

Sample Input

1
daBcd
ABC

Sample Output

YES

Explanation

image

We have daBcd and ABC. We perform the following operation:

  1. Capitalize the letters a and c in so that dABCd.
  2. Delete all the remaining lowercase letters in so that ABC.

Because we were able to successfully convert to , we print YES on a new line.

Limbajul de programare folosit: java8

Cod:

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int q = sc.nextInt();
		for (int tc = 0; tc < q; tc++) {
			String a = sc.next();
			String b = sc.next();

			System.out.println(solve(a, b) ? "YES" : "NO");
		}

		sc.close();
	}

	static boolean solve(String a, String b) {
		boolean[][] possibles = new boolean[a.length() + 1][b.length() + 1];
		for (int lengthA = 0; lengthA <= a.length(); lengthA++) {
			for (int lengthB = 0; lengthB <= b.length(); lengthB++) {
				if (lengthA == 0) {
					if (lengthB == 0) {
						possibles[lengthA][lengthB] = true;
					} else {
						possibles[lengthA][lengthB] = false;
					}
				} else {
					char lastA = a.charAt(lengthA - 1);

					if (lengthB == 0) {
						if (Character.isLowerCase(lastA)) {
							possibles[lengthA][lengthB] = possibles[lengthA - 1][lengthB];
						} else {
							possibles[lengthA][lengthB] = false;
						}
					} else {
						char lastB = b.charAt(lengthB - 1);

						if (Character.isLowerCase(lastA)) {
							if (Character.toUpperCase(lastA) == lastB) {
								possibles[lengthA][lengthB] = possibles[lengthA - 1][lengthB]
										|| possibles[lengthA - 1][lengthB - 1];
							} else {
								possibles[lengthA][lengthB] = possibles[lengthA - 1][lengthB];
							}
						} else {
							if (lastA == lastB) {
								possibles[lengthA][lengthB] = possibles[lengthA - 1][lengthB - 1];
							} else {
								possibles[lengthA][lengthB] = false;
							}
						}
					}
				}
			}
		}
		return possibles[a.length()][b.length()];
	}
}

Scor obtinut: 1.0

Submission ID: 464603407

Link challenge: https://www.hackerrank.com/challenges/abbr/problem

Abbreviation