Assignment 3 #

This assignment is about implementing a simple pattern matching algorithm.

Description #

We have discussed Dynamic Programming in the lecture. In this assignment, please analyse the question and build proper Dynamic Programming algorithm.

We are building an algorithm to find if the text matches the pattern. The patterns might include two type of wildcards, ? and *. The ? wildcard can match any single character. The * wildcard can match any string (including empty string).

For example:

• text abc matches pattern a?c
• text abc matches pattern a*c
• text abc matches pattern *
• text abc matches pattern a*
• text abc matches pattern *c
• text abc does not match pattern bc

The text and the pattern needs to be exactly matched, which means you are not allowed to match only part of the text or the pattern.

@FunctionalInterface
public interface PatternMatcherInterface {
    /**
     * Check if the text matches the pattern.
     * @param text The text to be matched.
     * @param pattern The pattern to be matched.
     * @return True if the text matches the pattern, false otherwise.
     */
    boolean match(String text, String pattern);
}

There are no competitions in this assignment. You shall implement your tests and ensure your implementation can pass all your tests.

Your implementation shall also pass hidden tests. The hidden tests will be used to evaluate your implementation along with your own tests. There are 2 points for passing the hidden tests.

Requirements #

• You need to write at least 3 different test cases. Do not test with large amount of data, or with multi-threading.
• You must use Dynamic Programming to solve the problem.

Submission #

It is extremely important that you are following the naming conventions for your class, tests, files, and submissions. If the automatic system fails to recognise your submissions or failed to execute them, your assignment will be treated as NOT SUBMITTED. Late submissions are NOT allowed and will NOT be accepted.

Requirements #

• Your submission must be a zip file and the file name must be your student number. Example: 202312345.zip
• Your submitted zip file must contain PatternMatcher.java and PatternMatcherTest<student number>.java. The structure shall like:

202312345.zip
	|- PatternMatcher.java
	|- PatternMatcherTest000000000.java

• The PatternMatcher.java file must include a public class, PatternMatcher, which extends the PatternMatcherInterface class.
• You can change anything in your submission.
• No third-party libraries or dependencies.
• Your code must be working with JDK 17 and up.
• All your own tests shall pass.
• Code style is important. You need to follow Java naming conventions and ensure there are no unnecessary extra new lines, spaces (e.g., additional spaces at the end of lines, a line with only spaces), etc.
• Do not declare packages. You must use the default package.

Validate your submission #

You can validate your submission here.

Passing the validation DOES NOT means your submission is correct. It only means your submission is in the correct format and can be executed by the automatic system. You still need to ensure your submission is correct.