Java DP AC. Same like Regular Expression Matching


  • 0
    R
    public class Solution {
        public boolean isMatch(String s, String p) {
                    if(s == null || p == null) {
                return false;
            }
            boolean[][] state = new boolean[s.length() + 1][p.length() + 1];
            state[0][0] = true;
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == '*' && state[0][j - 1]) {
                    
                        state[0][j] = true;
                } 
            }
            for (int i = 1; i < state.length; i++) {
                for (int j = 1; j < state[0].length; j++) {
                    if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                        state[i][j] = state[i - 1][j - 1];
                    }
                    if (p.charAt(j - 1) == '*') {
                            state[i][j] = state[i - 1][j] || state[i][j - 1] ;
                    }
                }
            }
            return state[s.length()][p.length()];
        }
    }
    
    

Log in to reply
 

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