Short and clean java code using DP and 1D array


  • 0
    S
    public class Solution {
        public boolean isMatch(String s, String p) {
            String[] patterns = new String[p.length()];
            int i = 0, ptr = 0;
            while (i != p.length()) {
                if (i + 1 < p.length() && p.charAt(i + 1) == '*') {
                    patterns[ptr++] = p.substring(i, i + 2);
                    i += 2;
                }
                else {
                    patterns[ptr++] = p.substring(i, i + 1);
                    i += 1;
                }
            }
            boolean[] d = new boolean[s.length() + 1];
            d[0] = true;
            for (i = 1; i <= s.length(); ++i) d[i] = false;
            for (i = 1; i <= ptr; ++i) {
                String pattern = patterns[i - 1];
                char c = pattern.charAt(0);
                if (pattern.length() == 2) {
                    for (int j = 1; j <= s.length(); ++j) {
                        d[j] = d[j] || (d[j - 1] && (c == '.' || c == s.charAt(j - 1)));
                    }
                }
                else {
                    for (int j = s.length(); j >= 1; --j) {
                        d[j] = d[j - 1] && (c == '.' || c == s.charAt(j - 1));
                    }
                }
                d[0] = d[0] && pattern.length() == 2;
            }
            return d[s.length()];
        }
    }

Log in to reply
 

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