Java: Match any single character (use ?) or any sequence of characters (use *) including the empty

Java Basic: Exercise-210 with Solution

String Matching with Wildcards

Write a Java program to match any single character (use ?) or any sequence of characters (use *) including empty. The matching should cover the entire input string.

Sample Example:

("bb","b") -> No
("bb","bb") -> Yes
("bbb","bb") -> No
("bb","?") -> No
("ab","?*") -> Yes
("bba","c*a*b") -> No

Visual Presentation:

Sample Solution:

Java Code:

import java.util.*;

public class PatternMatching {
    
    // Method for wildcard pattern matching
    static boolean pattern_match(String string, String pattern) {
        // i measures the length of the string
        int i = 0;
        // j measures the length of the pattern
        int j = 0;
        int star_index = -1;
        int i_index = -1;

        while (i < string.length()) {
            // If '?' matches the ith character of the string or if the jth character of the
            // pattern matches the ith character of the string. e.g. (a & ?), (ab & ab)
            if (j < pattern.length() && (pattern.charAt(j) == '?' || pattern.charAt(j) == string.charAt(i))) {
                ++i;
                ++j;
            } 
            // Counts '*' characters of the pattern when the count of the string is not
            // completed yet. e.g. (a & ***), (abb & ab****)
            else if (j < pattern.length() && pattern.charAt(j) == '*') {
                star_index = j;
                i_index = i;
                j++;
            } 
            // Counts the characters of the string which are left out once a '*' of the pattern 
            // gets counted e.g. (xayb & *a*b), (a & ***), (abcd & ab*), (aa & ?**)
            else if (star_index != -1) {
                j = star_index + 1;
                i = i_index + 1;
                i_index++;
            } 
            // If the characters of the string and pattern don't match
            // e.g. (xy & ab), (abxy & ab)
            else {
                return false;
            }
        }

        // Counts the '*' characters of the pattern when the characters before the '*' characters
        // of the pattern completely match the string and both are of the same length
        // (apart from the '*' characters of the pattern)
        // e.g. (ab and ab**), (aa and ??**)
        while (j < pattern.length() && pattern.charAt(j) == '*') {
            ++j;
        } 

        return j == pattern.length();
    }

    public static void main(String args[]) { 
        String str, pat;
        Scanner in = new Scanner(System.in);
        System.out.println("Enter a string");
        str = in.nextLine();
        System.out.println("Enter a pattern");
        pat = in.nextLine();
        if (pattern_match(str, pat))
            System.out.println("Yes"); 
        else
            System.out.println("No");
    }  
} 

Sample Output:

Enter a string
 bb
Enter a pattern
 b*
Yes

Flowchart:

Java Code Editor:

Company:  Google Facebook Twitter Snapchat Two Sigma

Contribute your code and comments through Disqus.

Previous: Write a Java program to find all unique combinations from a collection of candidate numbers.
Next: Write a Java program to find heights of the top three building in descending order from eight given buildings.