WildcardMatching Added (TheAlgorithms#4404)

janmeshjs · web-flow · commit 566c27a996f4 · 2023-09-27T12:54:52.000+03:00
* Added WildcardMatching DP

* Wildcard Matching update

* Updated WildcardMatching

* Added WildcardMatchingTests

* WildcardMatching update

* Clang-formatting done

* WildcardMatching_Clang-formatting done

* WildcardMatching
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/WildcardMatching.java 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];
+    }
+}
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/WildcardMatchingTest.java 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", ""));
+    }
+}
