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.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Abbreviation
  5. Discussions

Abbreviation

  • beat1Percent
     + 9 comments

    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:

    1. 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].

    1. 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:

    import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the abbreviation function below.
    static String abbreviation(String a, String b) {
        boolean[][] dp = new boolean[b.length() + 1][a.length() + 1];
        dp[0][0] = true;
        for (int j = 1; j < dp[0].length; j++) {
            if (Character.isLowerCase(a.charAt(j - 1))) dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                char ca = 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];
                    else dp[i][j] = dp[i][j - 1];
                }
            }
        }
        
        return dp[b.length()][a.length()] ? "YES" : "NO";
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String a = scanner.nextLine();

            String b = scanner.nextLine();

            String result = abbreviation(a, b);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}