package com.fishercoder.solutions;

/**
 * 44. 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", "c*a*b") → false
 */
public class _44 {

  public static class Solution1 {
    public boolean isMatch(String s, String p) {
      boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
      match[s.length()][p.length()] = true;
      for (int i = p.length() - 1; i >= 0; i--) {
        if (p.charAt(i) != '*') {
          break;
        } else {
          match[s.length()][i] = true;
        }
      }

      for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = p.length() - 1; j >= 0; j--) {
          if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
            match[i][j] = match[i + 1][j + 1];
          } else if (p.charAt(j) == '*') {
            match[i][j] = match[i + 1][j] || match[i][j + 1];
          } else {
            match[i][j] = false;
          }
        }
      }
      return match[0][0];
    }
  }
}

@@ -33,581 +33,8 @@
 s;%0A%0A
-/**%0A * 44. Wildcard Matching%0A * Implement wildcard pattern matching with support for '?' and '*'.%0A%0A '?' Matches any single character.%0A '*' Matches any sequence of characters (including the empty sequence).%0A%0A The matching should cover the entire input string (not partial).%0A%0A The function prototype should be:%0A bool isMatch(const char *s, const char *p)%0A%0A Some examples:%0A isMatch(%22aa%22,%22a%22) %E2%86%92 false%0A isMatch(%22aa%22,%22aa%22) %E2%86%92 true%0A isMatch(%22aaa%22,%22aa%22) %E2%86%92 false%0A isMatch(%22aa%22, %22*%22) %E2%86%92 true%0A isMatch(%22aa%22, %22a*%22) %E2%86%92 true%0A isMatch(%22ab%22, %22?*%22) %E2%86%92 true%0A isMatch(%22aab%22, %22c*a*b%22) %E2%86%92 false%0A */%0A
 publ
@@ -49,16 +49,18 @@
  _44 %7B%0A%0A
+  
   public
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     publ
@@ -134,24 +134,30 @@
 String p) %7B%0A
+      
       boolea
@@ -211,24 +211,30 @@
 gth() + 1%5D;%0A
+      
       match%5B
@@ -261,24 +261,30 @@
 ()%5D = true;%0A
+      
       for (i
@@ -313,32 +313,40 @@
  i %3E= 0; i--) %7B%0A
+        
         if (p.ch
@@ -355,32 +355,42 @@
 At(i) != '*') %7B%0A
+          
           break;
@@ -390,32 +390,40 @@
  break;%0A        
+      
+  
 %7D else %7B%0A       
@@ -407,32 +407,42 @@
        %7D else %7B%0A
+          
           match%5B
@@ -476,19 +476,39 @@
     
-%7D%0A
+        %7D%0A    
       
+  
 %7D%0A%0A
+      
     
@@ -553,32 +553,40 @@
  i--) %7B%0A        
+    
+    
 for (int j = p.l
@@ -619,24 +619,34 @@
 %7B%0A          
+       
+   
 if (s.charAt
@@ -685,24 +685,36 @@
 ) == '?') %7B%0A
+            
             
@@ -754,24 +754,34 @@
 ;%0A          
+         
+ 
 %7D else if (p
@@ -793,32 +793,44 @@
 At(j) == '*') %7B%0A
+            
             matc
@@ -867,32 +867,42 @@
 atch%5Bi%5D%5Bj + 1%5D;%0A
+          
           %7D else
@@ -908,32 +908,44 @@
 e %7B%0A            
+ 
+           
 match%5Bi%5D%5Bj%5D = fa
@@ -959,26 +959,39 @@
         
-%7D%0A
+          %7D%0A   
         
 %7D%0A      
@@ -982,24 +982,29 @@
         
+     
 %7D%0A      
 %7D%0A      
@@ -995,24 +995,30 @@
 %7D%0A      
+ 
+     
 %7D%0A      
 return m
@@ -1009,16 +1009,22 @@
 %7D%0A      
+ 
+     
 return m
@@ -1039,16 +1039,22 @@
 0%5D;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 44