5ms JAVA DP and O(n) Space Solution


  • 0
    public boolean isMatch(String s, String p) {
        
        if ((s == null || s.length() == 0) && (p == null || p.length() == 0)) return true;
        if (p == null || p.length() == 0) return false;
        
        int m = s.length();
        int n = p.length();
        
        boolean[] f = new boolean[n + 1];
        
        f[0] = true;
        
        for (int j = 2; j <= n; j++) {
            f[j] = p.charAt(j - 1) == '*' && f[j - 2];
        }
        
        boolean upleft; // for f[i - 1][j -1]
        
        for (int i = 1; i <= m; i++) {
            upleft = f[0];
            f[0] = false;
            for (int j = 1; j <= n; j++) {
                char cs = s.charAt(i - 1);
                char cp = p.charAt(j - 1);
                boolean up = f[j]; // for f[i -1][j]
                if (cp == '*') {
                    f[j] = j >= 2 && (f[j - 2] || ((p.charAt(j - 2) == cs || p.charAt(j - 2) == '.') && f[j]));
                } else {
                    f[j] = upleft && (cs == cp || cp == '.');
                }
                upleft = up;
                
            }
        }
        return f[n];
        
    }

Log in to reply
 

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