You can perform the following operation on some string a:
Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase).
Delete all of the remaining lowercase letters in a.
Given string a, print YES if it can be transformed to string b.
String a has only capital and small letter alphabets.
String b has only capital letters.
THIS is the link to the problem.
Example:
a: daBcd
b: ABC
OUTPUT: YES
This passed all the test-cases. But I wanted to know if any further optimizations can be made or not. Maybe I am using redundant conditions or something like this.
//n is the length of the string a
//m is the length of the string b
public static void func(char[] a,int n, char[] b, int m)
{
int[][] mat = new int[n + 1][m + 1];
for(int i = 0 ; i < n + 1 ; i++)
mat[i][0] = 0;
for(int i = 0 ; i < m + 1 ; i++)
mat[0][i] = 0;
char capStart = 65;
char capEnd = 90;
char smallStart = 97;
char smallEnd = 122;
char diff = 32;
for(int i = 1 ; i < n + 1 ; i++)
{
for(int j = 1 ; j < m + 1 ; j++)
{
if(a[i - 1] >= smallStart)
{
if(a[i - 1] - diff == b[j - 1])
{
if(mat[i - 1][j] == j)
mat[i][j] = mat[i - 1][j];
else
mat[i][j] = 1 + mat[i - 1][j - 1];
}
else
{
if(mat[i - 1][j] == j || mat[i][j - 1] == j)
mat[i][j] = j;
else
mat[i][j] = Math.max(mat[i - 1][j],mat[i][j - 1]);
}
}
else
{
if(a[i - 1] == b[j - 1])
{
mat[i][j] = 1 + mat[i - 1][j - 1];
}
else
{
mat[i][j] = mat[i][j - 1];
}
}
}
}
if(mat[n][m] == m)
System.out.println("YES");
else
System.out.println("NO");
}
If you want, you can check your solution for 1 of the sample inputs:
Input format:
First line contains an integer q showing the number of pairs of a and b. Next 2q lines for a and b.
10
Pi
P
AfPZN
APZNC
LDJAN
LJJM
UMKFW
UMKFW
KXzQ
K
LIT
LIT
QYCH
QYCH
DFIQG
DFIQG
sYOCa
YOCN
JHMWY
HUVPW
Output:
YES
NO
NO
YES
NO
YES
YES
YES
NO
NO
