My Java code, both DP and recursive


  • 1
    T

    pretty standard, nothing special. maybe the only thing to note is to let the "empty string vs ...* pattern" case handle itself , by setting the starting point of i=0 instead of 1 (which would not consider empty strings)

    public class Solution {
        public boolean isMatch(String s, String p) {
            char [] ss = s.toCharArray();
            char [] pp = p.toCharArray();
            // return recursive(ss, 0, pp, 0);
            boolean ans[][] = new boolean[ss.length+1][pp.length+1];
            
            ans[0][0] = true; // empty string empty pattern
            for(int i=0;i<=ss.length;i++) {
                //default ans[i][0] = false; for all i > 0 //  non-empty string, empty pattern
                for(int j=1;j<=pp.length;j++) {
                    if (pp[j-1] != '*' ) {
                        ans[i][j] = i > 0 && matches(ss[i-1], pp[j-1]) && ans[i-1][j-1];
                    } else {
                        ans[i][j] = j >=2 && (
                                   ans[i][j-2] || 
                                   (i > 0 && matches(ss[i-1], pp[j-1  -1])  && ans[i-1][j])
                                   );
                    }
                }
            }
            return ans[ss.length][pp.length];
        }
        
        boolean recursive(char[] s, int i, char[] p, int j) {
            if (i == s.length && j == p.length) return true;
            if (j == p.length) return false;
            
           if (j< p.length-1 && p[j+1] == '*') {
               
                   return recursive(s, i, p, j+2) || i < s.length  && matches(s[i],p[j]) && recursive(s, i+1, p, j);
               
           } else 
           return  i < s.length && matches(s[i], p[j]) && recursive(s,i+1, p, j+1);
        }
        
        boolean matches(char c, char p) {
            if (p == '.') return true;
            else return c == p;
        }
    }

  • 0
    M

    What would be the result for 'recursive' if s is "a" and b is "*a" ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.