44. Wildcard Matching

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char s, const char p)

Some examples: isMatch("aa","a") ? false isMatch("aa","aa") ? true isMatch("aaa","aa") ? false isMatch("aa", "") ? true isMatch("aa", "a") ? true isMatch("ab", "?") ? true isMatch("aab", "ca*b") ? false

Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;

        if (s.equals(p)) {
            return true;
        }

        int i = 0;
        int j = 0;
        int startIndex = -1;
        int tempIIndex = -1;


        while (i < s.length()) {

            if (j < p.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
                i ++;
                j ++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                startIndex = j;
                tempIIndex = i;
                j++;
            } else if (startIndex != -1) {
                j = startIndex + 1;
                i = tempIIndex +1;
                tempIIndex ++;
            } else {
                return false;
            }
        }

        while (j<p.length() &&p.charAt(j) == '*') {
            j ++;
        }

        return j == p.length();

    }
}