Workable (not the fastest) solution for https://leetcode.com/problems/regular-expression-matching/

dp-solution-for-regular-expression-leetcode.java

class Solution {
    
    private final static char NULL_CHAR = '_';
    private final static int PADDING = 1;
    
    public boolean isMatch(String s, String p) {
        final List<String> pattern = extractPattern(p);
        
        // System.out.println(String.format("Search string: %s", s));
        // System.out.println(String.format("Regex pattern: %s", pattern));
        
        // Note: Padding to the string is extremely important for the case such as:
        // s: ""
        // p: ".*"
        final boolean[][] dpMap = new boolean[pattern.size()][s.length() + PADDING];
        traverseBottomUp(s, pattern, dpMap);
        
        // System.out.println(String.format("%s", toPrettyString(dpMap, s, pattern)));
        
        return safeGet(dpMap, pattern.size() - 1, s.length());
    }
    
    /**
     * Represent the graph as a list of expression string.
     * e.g., ["m","i","s*","."]
     */
    private List<String> extractPattern(
        String p
    ) {
        final List<String> graph = new ArrayList<String>();
        
        int end = p.length();
        final int lastIndex = p.length() - 1;
        for (int i = lastIndex; i >= 0; --i) {
            final char c = p.charAt(i);
            if (c >= 'a' && c <= 'z' || c == '.') {
                graph.add(0, p.substring(i, end));
                end = i;
            } else if (c == '*') {
                // No-op
            } else {
                throw new IllegalArgumentException();
            }
        }
        
        return graph;
    }
    
    private void traverseBottomUp(
        String searchStr,
        List<String> pattern,
        boolean[][] dpMap
    ) {
        for (int i = 0; i < pattern.size(); ++i) {
            final String expr = pattern.get(i);
            final char exprChar = expr.charAt(0);
            
            for (int j = 0; j <= searchStr.length(); ++j) {
                final int actualIndex = j - PADDING;
                final boolean notPadding = actualIndex >= 0;
                final char c;
                // First element is the padding to denote null character.
                if (notPadding) {
                    c = searchStr.charAt(actualIndex);
                } else {
                    c = NULL_CHAR;
                }
                
                if (expr.length() == 1) {
                    // Case as alphabet.
                    if (notPadding &&
                        (exprChar == '.' || exprChar == c)) {
                        // Check the remaining string and pattern without this pair.
                        final boolean restWithoutThis = safeGet(dpMap, i - 1, j - 1);
                        
                        dpMap[i][j] = restWithoutThis;
                    } else {
                        // dpMap[i][j] = false; // Not necessary since the field is
                        // initialized as false!
                    }
                } else {
                    // Case as optional alphabet. e.g., "p*" or ".*"
                    
                    // 0 occurance, check the result (solved) without this pattern.
                    final boolean withoutOccur = safeGet(dpMap, i - 1, j);
                    
                    // With occurance.
                    final boolean matched = exprChar == '.' || exprChar == c;
                    final boolean withOccur = matched && safeGet(dpMap, i, j - 1);
                    
                    dpMap[i][j] = withoutOccur || withOccur;
                }
            }
        }
    }
    
    private boolean safeGet(
        boolean[][] dpMap,
        int exprIndex,
        int searchCharIndex
    ) {
        if (exprIndex < 0 && searchCharIndex < 1) {
            return true;
        } else {
            if (exprIndex < 0) {
                // Case as no pattern to match. XD
                return false;
            } else if (searchCharIndex < 0) {
                // Case as Empty char to compare
                return false;
            } else {
                // Both expr index and search index are positive.
                return dpMap[exprIndex][searchCharIndex];
            }
        }
    }
    
    private String toPrettyString(
        boolean[][] dpMap,
        String searchStr,
        List<String> pattern
    ) {
        final StringBuilder sb = new StringBuilder();
        
        // Header
        for (int i = 0; i < pattern.size(); ++i) {
            final String expr = pattern.get(i);
            if (i == 0) {
                sb.append("   ");
            }
            
            sb.append(String.format("%8s", expr));
            
            if (i == pattern.size() - 1) {
                sb.append("\n");
            }
        }
        
        for (int j = 0; j <= searchStr.length(); ++j) {
            final int actualIndex = j - PADDING;
            final char c;
            if (actualIndex >= 0) {
                c = searchStr.charAt(actualIndex);
            } else {
                c = NULL_CHAR;
            }
            
            for (int i = 0; i < pattern.size(); ++i) {
                if (i == 0) {
                    sb.append(String.format("%3s", c));
                }
                
                sb.append(String.format("%8s", dpMap[i][j]));
                
                if (i == pattern.size() - 1) {
                    sb.append("\n");
                }
            }
        }
        
        return sb.toString();
    }
}