We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
What we need to solve is, regardless of the case, if b is a subsequence of a with the constraint that a can only discard lower case characters. Therefore, if we want to know if b[0, i] is an abbreviation of a[0, j], we have two cases to consider:
a[j] is a lower case character.
if uppercase(a[j]) == b[i], either b[i - 1]is an abbreviation of a[0, j - 1] or b[i - 1] is an abbreviation of a[0, j], b[0, i] is an abbreviation of a[0, j].
else if b[0, i] is an abbreviation of a[0, j -1], b[0, i] is an abbreviation of a[0, j].
else, b[0, i] cannot be an abbreviation of a[0, j].
a[j] is a upper case character.
if a[j] == b[i] and b[0, i - 1] is an abbreviation of a[0, j - 1], b[0, i] is an abbreviation of a[0, j].
else b[0, i] cannot be an abbreviation of a[0, j].
Below is a Java solution:
importjava.io.*;importjava.math.*;importjava.security.*;importjava.text.*;importjava.util.*;importjava.util.concurrent.*;importjava.util.regex.*;publicclassSolution{// Complete the abbreviation function below.staticStringabbreviation(Stringa,Stringb){boolean[][]dp=newboolean[b.length()+1][a.length()+1];dp[0][0]=true;for(intj=1;j<dp[0].length;j++){if(Character.isLowerCase(a.charAt(j-1)))dp[0][j]=dp[0][j-1];}for(inti=1;i<dp.length;i++){for(intj=1;j<dp[0].length;j++){charca=a.charAt(j-1),cb=b.charAt(i-1);if(ca>='A'&&ca<='Z'){if(ca==cb){dp[i][j]=dp[i-1][j-1];}}else{ca=Character.toUpperCase(ca);if(ca==cb)dp[i][j]=dp[i-1][j-1]||dp[i][j-1];elsedp[i][j]=dp[i][j-1];}}}returndp[b.length()][a.length()]?"YES":"NO";}privatestaticfinalScannerscanner=newScanner(System.in);publicstaticvoidmain(String[]args)throwsIOException{BufferedWriterbufferedWriter=newBufferedWriter(newFileWriter(System.getenv("OUTPUT_PATH")));intq=scanner.nextInt();scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");for(intqItr=0;qItr<q;qItr++){Stringa=scanner.nextLine();Stringb=scanner.nextLine();Stringresult=abbreviation(a,b);bufferedWriter.write(result);bufferedWriter.newLine();}bufferedWriter.close();scanner.close();}}
Abbreviation
You are viewing a single comment's thread. Return to all comments →
What we need to solve is, regardless of the case, if
b
is a subsequence ofa
with the constraint thata
can only discard lower case characters. Therefore, if we want to know ifb[0, i]
is an abbreviation ofa[0, j]
, we have two cases to consider:a[j]
is a lower case character.if
uppercase(a[j]) == b[i]
, eitherb[i - 1]
is an abbreviation ofa[0, j - 1]
orb[i - 1]
is an abbreviation ofa[0, j]
,b[0, i]
is an abbreviation ofa[0, j]
.else if
b[0, i]
is an abbreviation ofa[0, j -1]
,b[0, i]
is an abbreviation ofa[0, j]
.else,
b[0, i]
cannot be an abbreviation ofa[0, j]
.a[j]
is a upper case character.if
a[j] == b[i]
andb[0, i - 1]
is an abbreviation ofa[0, j - 1]
,b[0, i]
is an abbreviation ofa[0, j]
.else
b[0, i]
cannot be an abbreviation ofa[0, j]
.Below is a Java solution: