package com.interview.dynamic;

/**
 * Date 02/11/2016
 * @author Tushar Roy
 *
 * Wild car matching with ? and *
 *
 * Reference
 * https://leetcode.com/problems/wildcard-matching/
 */
public class WildCardMatching {
    public boolean isMatch(String s, String p) {
        char[] text = s.toCharArray();
        char[] pattern = p.toCharArray();

        int writeIndex = 0;
        boolean isFirst = true;
        for ( int i = 0 ; i < pattern.length; i++) {
            if (pattern[i] == '*') {
                if (isFirst) {
                    pattern[writeIndex++] = pattern[i];
                    isFirst = false;
                }
            } else {
                pattern[writeIndex++] = pattern[i];
                isFirst = true;
            }
        }

        boolean T[][] = new boolean[text.length + 1][writeIndex + 1];

        if (writeIndex > 0 && pattern[0] == '*') {
            T[0][1] = true;
        }

        T[0][0] = true;

        for (int i = 1; i < T.length; i++) {
            for (int j = 1; j < T[0].length; j++) {
                if (pattern[j-1] == '?' || text[i-1] == pattern[j-1]) {
                    T[i][j] = T[i-1][j-1];
                } else if (pattern[j-1] == '*'){
                    T[i][j] = T[i-1][j] || T[i][j-1];
                }
            }
        }

        return T[text.length][writeIndex];
    }


    /**
     * Recursive and slow version of wild card matching.
     */
    public boolean isMatchRecursive(String s, String p) {
        return isMatchRecursiveUtil(s.toCharArray(), p.toCharArray(), 0, 0);
    }

    private boolean isMatchRecursiveUtil(char[] text, char[] pattern, int pos1, int pos2) {
        if (pos2 == pattern.length) {
            return text.length == pos1;
        }

        if (pattern[pos2] != '*') {
            if (pos1 < text.length && (text[pos1] == pattern[pos2]) || pattern[pos2] == '?') {
                return isMatchRecursiveUtil(text, pattern, pos1 + 1, pos2 + 1);
            } else {
                return false;
            }
        } else {
            //if we have a***b then skip to the last *
            while (pos2 < pattern.length - 1 && pattern[pos2 + 1] == '*') {
                pos2++;
            }
            pos1--;
            while (pos1 < text.length) {
                if (isMatchRecursiveUtil(text, pattern, pos1 + 1, pos2 + 1)) {
                    return true;
                }
                pos1++;
            }
            return false;
        }
    }
}

@@ -275,20 +275,19 @@
  char%5B%5D 
-text
+str
  = s.toC
@@ -341,16 +341,89 @@
 ray();%0A%0A
+        //replace multiple * with one *%0A        //e.g a**b***c --%3E a*b*c%0A
         
@@ -872,20 +872,19 @@
 boolean%5B
-text
+str
 .length 
@@ -1161,20 +1161,19 @@
  '?' %7C%7C 
-text
+str
 %5Bi-1%5D ==
@@ -1395,20 +1395,19 @@
 eturn T%5B
-text
+str
 .length%5D
@@ -2533,32 +2533,32 @@
   return false;%0A
-
         %7D%0A    %7D%0A
@@ -2556,11 +2556,178 @@
  %7D%0A    %7D
+%0A%0A    public static void main(String args%5B%5D) %7B%0A        WildCardMatching wcm = new WildCardMatching();%0A        System.out.println(wcm.isMatch(%22xbylmz%22, %22x?y*z%22));%0A    %7D
 %0A%7D%0A

update wildcard