Java DP O(mn) time O(n) space with rolling array trick


  • 0
    public class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length(), n = p.length();
            boolean[][] match = new boolean[2][n + 1];
            match[0][0] = true;
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (j == 0) { // initialized first column
                        match[i % 2][j] = i == 0;
                        continue;
                    }
                    if (p.charAt(j - 1) == '*') {
                        match[i % 2][j] = (i > 0 && match[(i - 1) % 2][j]) || match[i % 2][j - 1];
                    } else {
                        match[i % 2][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') && match[(i - 1) % 2][j - 1];
                    }
                    
                }
            }
            return match[m % 2][n];
        }
    }

Log in to reply
 

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