My Java accepted solution. Parsing expression to tokens then use DP


  • 2
    Z

    I parsed the expression into tokens like "a", "." and "a*" and then used dp for matching the string with the tokens. match[i][j] represents whether s.substring(0, i) matches with the tokens from index 0 to index j-1.

    public class Solution {
        public boolean isMatch(String s, String p) {
            if (s == null && p == null || s.length() == 0 && p.length() == 0) {
              return true;
            }
            if (s == null || p == null) {
              return false; 
            }
            List<String> tokens = parse(p);
            boolean[][] match = new boolean[s.length()+1][tokens.size()+1];
            match[0][0] = true;
            int match_len = s.length() + 1;
            int token_len = tokens.size() + 1;
    
            // Initialize match for dp iteration
            for (int i = 1; i < match_len; i++) {
              match[i][0] = false;
            }
            for (int i = 1; i < token_len; i++) {
              match[0][i] = match[0][i-1] && tokens.get(i-1).length() == 2;
            }
    
            // dp
            for (int i = 1; i < match_len; i++) {
              for (int j = 1; j < token_len; j++) {
                String curr = tokens.get(j-1);
                match[i][j] = curr.length() == 2 && match[i][j-1] || 
                              curr.length() == 2 && (curr.charAt(0) == '.' || curr.charAt(0) == s.charAt(i-1)) && match[i-1][j] ||
                              (curr.charAt(0) == '.' || curr.charAt(0) == s.charAt(i-1)) && match[i-1][j-1];
              }
            }
            return match[match_len-1][token_len-1];
        }
    
        // Parse the expression into length one or length two tokens.
        public List<String> parse(String p) {
            int i = 0;
            List<String> result = new ArrayList<String>(); 
            while (i < p.length()) {
                if (p.charAt(i) == '*') {
                    i++;
                } else {
                    if (i + 1 >= p.length() || p.charAt(i+1) != '*') {
                        result.add(p.substring(i, i+1));
                        i++;
                    } else if (p.charAt(i+1) == '*') {
                        result.add(p.substring(i, i+2));
                        i += 2;
                    }
                }
            }
            return result;
        }
    
    
    }

  • 0
    L

    I really don't know how this solution is accepted..
    I couldn't type it out, because the 'star' character will be automatically omitted by the system after I submitted the commet. So, I use [star] instead of typing it, try this:
    s = "[star]ac", p ="[star]a.[star]"
    Apparently, they match! But this solution returns false. Check it out.


Log in to reply
 

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