Repository: TheAlgorithms/Java
Pull request #4404 (2023-09-25 20:20:58)

WildcardMatching Added
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


janmeshjs: Added JUnit tests for the review. 
janmeshjs: I tried reformatting but the error with clang format still persist. 
BamaCharanChhandogi: Try to solve the clang issue. 
The `-` sign means you have to remove that line from your code. and `+` sign means you have to add that line.
janmeshjs: All issues resolved. Thank you.
@siriak @BamaCharanChhandogi 
janmeshjs: > Please remove `main`, it's redundant

Done! Please let me know if any other changes are required.

Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/WildcardMatching.java b/src/main/java/com/thealgorithms/dynamicprogramming/WildcardMatching.java
new file mode 100644
index 00000000..a938634c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/WildcardMatching.java
@@ -0,0 +1,55 @@
+/**
+ *
+ * Author: Janmesh Singh
+ * Github: https://github.com/janmeshjs
+
+ * Problem Statement: To determine if the pattern matches the text.
+ * The pattern can include two special wildcard characters:
+ *       ' ? ': Matches any single character.
+ *       ' * ': Matches zero or more of any character sequence.
+ *
+ * Use DP to return True if the pattern matches the entire text and False otherwise
+ *
+ */
+
+package com.thealgorithms.dynamicprogramming;
+
+public class WildcardMatching {
+
+    public static boolean isMatch(String text, String pattern) {
+        int m = text.length();
+        int n = pattern.length();
+
+        // Create a DP table to store intermediate results
+        boolean[][] dp = new boolean[m + 1][n + 1];
+
+        // Base case: an empty pattern matches an empty text
+        dp[0][0] = true;
+
+        // Handle patterns starting with '*'
+        for (int j = 1; j <= n; j++) {
+            if (pattern.charAt(j - 1) == '*') {
+                dp[0][j] = dp[0][j - 1];
+            }
+        }
+
+        // Fill the DP table
+        for (int i = 1; i <= m; i++) {
+            for (int j = 1; j <= n; j++) {
+                char textChar = text.charAt(i - 1);
+                char patternChar = pattern.charAt(j - 1);
+
+                if (patternChar == textChar || patternChar == '?') {
+                    dp[i][j] = dp[i - 1][j - 1];
+                } else if (patternChar == '*') {
+                    // '*' can match zero or more characters
+                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
+                } else {
+                    dp[i][j] = false;
+                }
+            }
+        }
+        // The result is in the bottom-right cell of the DP table
+        return dp[m][n];
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/WildcardMatchingTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/WildcardMatchingTest.java
new file mode 100644
index 00000000..8d91af66
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/WildcardMatchingTest.java
@@ -0,0 +1,26 @@
+package com.thealgorithms.dynamicprogramming;
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+public class WildcardMatchingTest {
+
+    @Test
+    public void testMatchingPattern() {
+        assertTrue(WildcardMatching.isMatch("aa", "a*"));
+        assertTrue(WildcardMatching.isMatch("adceb", "*a*b"));
+    }
+
+    @Test
+    public void testNonMatchingPattern() {
+        assertFalse(WildcardMatching.isMatch("cb", "?a"));
+        assertFalse(WildcardMatching.isMatch("acdcb", "a*c?b"));
+        assertFalse(WildcardMatching.isMatch("mississippi", "m*issi*iss?*i"));
+    }
+
+    @Test
+    public void testEmptyPattern() {
+        assertTrue(WildcardMatching.isMatch("", ""));
+        assertFalse(WildcardMatching.isMatch("abc", ""));
+    }
+}