Java solution which beats 96% with some explains.


  • 0
    L

    DFS and Dynamic programming

    public class Solution {
        static String ss;
        static String pp;
        static int[][] map;
    
        public boolean isMatch(String s, String p) {
            ss = s;
            pp = p;
            map = new int[s.length()+1][p.length()+1];
    
            return helper(0, 0);
        }
    
        private boolean helper(int i, int j) {
            if (map[i][j] != 0)
                return (map[i][j]>0) ? true : false;
    
            boolean ret;    
            if (i < ss.length() && j == pp.length()) {
                ret = false;
            } else if (i == ss.length()) {
                switch (pp.length()-j) {
                    case 0:
                        ret = true;
                        break;
                    case 1:
                        ret = false;
                        break;
                    default:
                        if (pp.charAt(j+1) == '*')
                            ret = helper(i, j+2);
                        else {
                            ret = false;
                        }
                        break;
                }
            } else if (pp.length()-j >= 2 && pp.charAt(j+1) == '*') {
                if (pp.charAt(j) == '.' || ss.charAt(i) == pp.charAt(j)) {
                    // (to match and retain regex) or (to match and skip regex) or (no to match and skip regex)
                    ret = helper(i+1, j) || helper(i+1, j+2) || helper(i, j+2);
                } else
                    // not match and skip regex
                    ret = helper(i, j+2);
            } else {
                if (pp.charAt(j) == '.' || ss.charAt(i) == pp.charAt(j)) {
                    ret = helper(i+1, j+1);
                } else {
                    ret = false;
                }
            }
    
            map[i][j] = ret?1:-1;
            return ret;
        }
    }
    

Log in to reply
 

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